剑指 Offer - 15 - 反转链表

Question

题目

输入一个链表，反转链表后，输出新链表的表头。

解析

这个题目和 LeetCode206 是一样的。解析也可以看那篇博客。两种思路:

思路一：

• 很经典的翻转链表的题目，使用 pre、next 指针， pre 指向当前 cur 的前一个， next 是当前 cur 的下一个指针；
• 然后每次都改变 cur 的 next 为 pre，循环递推，直到 cur = null ，最后返回 pre ；

public class Solution {
    
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null, cur = head, next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;//反转
            pre = cur;//继续下一次
            cur = next;
        }
        return pre;
    }
}

思路二：递归

思路和上面还是一样的，就是 pre = cur，cur = next 这两行替换成去递归了，没什么特殊的。

public class Solution {

    public ListNode ReverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode cur, ListNode pre) {
        if (cur == null)
            return pre;
        ListNode next = cur.next;
        cur.next = pre;
        return reverse(next, cur);
    }
}