反转链表

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

代码

个人方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public ListNode reverseList(ListNode head) {
    //如果不必要交换，直接返回
    if(head==null||head.next==null)return head;
    //定义前一个节点
    ListNode pre=head;
    //正在操作的节点
    ListNode now=head.next;
    //后一个节点
    ListNode suf=now.next;
    //如果后一个节点不为null
    while(suf!=null){
        //交换节点
        now.next=pre;
        //交换之后只需要保存原本在后的节点即可
        pre=now;
        //移动目前正在操作的节点到下一个节点
        now=suf;
        //下一个节点移动到下一个的下一个节点
        suf=suf.next;
    }
    //由于最后一次因为suf==null没有执行交换
    now.next=pre;
    //将原本头节点的下一个节点引用变为null
    head.next=null;
    //返回当前操作的节点，也就是最后一个节点
    return now;
}

迭代

​ 在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    ListNode nextTemp = null;
    while (curr != null) {
        nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

递归

递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？假设列表为：n1 → … → nk-1 → nk → nk+1 → … → nm → Ø

若从节点 nk+1 到 nm 已经被反转，而我们正处于 nk。

n1 → … → nk-1 → nk → nk+1 ← … ← nm

我们希望 nk+1 的下一个节点指向 nk。

所以，nk.next.next = nk;

要小心的是 n1 的下一个必须指向 Ø 。如果你忽略了这一点，你的链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。

1
2
3
4
5
6
7
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}