使用Stack反转Java LinkedList时仅能反转部分元素如何解决

错误根因 #

你代码中反转功能少输出一个元素的核心原因是栈填充的循环判断逻辑错误：

• 原reverse方法中遍历链表的循环条件为while(current.next != null)，当遍历到链表最后一个节点时，该节点的next属性为null，循环会直接终止，最后一个节点的数值没有被压入栈中。因此输入3个元素时，栈中只会存入前2个元素，弹出时自然仅能输出2个反转结果。
• 额外说明：你当前实现的reverse方法本质是倒序打印链表，并没有修改原链表的节点指向关系，如果需要获得结构真正反转的链表，还需要补充节点重新拼接的逻辑。

修复代码 #

方案1：仅修复倒序打印问题 #

仅修改reverse方法的循环条件即可，修改后的reverse代码如下：

public static LinkedList reverse(LinkedList list){
    Stack<Integer> stack = new Stack<Integer>();
    Node current = list.head;
    // 把循环条件从current.next != null改为current != null，遍历所有节点
    while(current != null){
        stack.push(current.data);
        current = current.next;
    }
    System.out.println("The reversed list is: ");
    while(!stack.isEmpty()){
        System.out.print(stack.pop() + " ");
    }
    return list;
}

方案2：实现链表结构的真正反转 #

如果需要修改原链表结构完成反转，可参考如下实现：

public static LinkedList reverse(LinkedList list){
    Stack<Node> stack = new Stack<Node>();
    Node current = list.head;
    // 把所有节点压入栈
    while(current != null){
        stack.push(current);
        current = current.next;
    }
    // 栈为空直接返回
    if(stack.isEmpty()) return list;
    // 弹出栈顶节点作为新的头节点
    list.head = stack.pop();
    current = list.head;
    // 依次弹出剩余节点拼接成新链表
    while(!stack.isEmpty()){
        Node nextNode = stack.pop();
        current.next = nextNode;
        current = nextNode;
    }
    // 最后一个节点的next设为null，避免成环
    current.next = null;
    return list;
}

调用该方法后原链表的结构就会被真正反转，后续可直接遍历原链表得到反转后的结果。

内容的提问来源于stack exchange，提问作者sailesh kumar