如何在不影响原始链表的情况下反转链表？

Question

我想反转一个LinkedList，我写的基本程序如下：-

public class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){this.val = val;}
    ListNode(int val, ListNode next){this.val = val; this.next = next;}
}

   public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;  

        }
        return prev;
    }

这里是打印链表的程序

    public void print(ListNode curr){
        while(curr!=null){
            System.out.print(curr.val+" ");
            curr = curr.next;
        }
        System.out.println();
    }

现在我的名单是[1,2,21]

当我打印输出如下

1 2 3 1

当我反转打印头并反转输出如下：-

ListNode reversed = reverseList(head);
print(head);
print(reversed)

输出

1
1 3 2 1

有人能解释一下如何保持头部不变吗？

我试过反转链表。我成功了，但在颠倒列表后，它改变了我当前的列表。我想保持不变。

Answer 1

正如@tgdavies 已经评论的那样，您需要从头开始构建一个新列表。 从头到尾遍历原始列表， 边走边构建从尾到头的反向列表。

public ListNode reverseList(ListNode head) {
    ListNode reversed = null;
    ListNode curr = head;
    while (curr != null) {
        reversed = new ListNode(curr.val, reversed);
        curr = curr.next;
    }
    return reversed;
}

Answer 2

这听起来像是一个课堂项目。

试试这个：

1. 运行原始列表并将每个值存储在堆栈中。 当您完成原始列表时，堆栈（自上而下）将包含值 以相反的顺序。
2. 弹出堆栈并将值添加到新列表。