剑指Offer - 15 - 反转链表.md

剑指Offer - 15 - 反转链表

题目链接

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题目

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

解析

这个题目和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);
    }
}