LeetCode—206. 反转链表

• 一、题目描述
• • 1.1 示例
  • • 示例1
    • 示例2
    • 示例3
  • 1.2 提示
• 二、题目分析
• • 2.1 题目标签：链表
  • 2.2 解题思路—遍历
  • 2.3 解题思路—递归法
• 三、题解——Java
• • • 3.1 遍历
    • 3.2 递归

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]

输入：head = []
输出：[]

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

• 使用节点 cur 来记录每次被操作的链表节点；
• 使用节点 last 来记录当前节点 cur 的上一个节点，初始为 null；
• 使用节点 next 来记录当前节点 cur 的下一个节点；
• 每次操作先让 cur 指向 last，然后将 last 移向 cur 的位置；
• 再让 cur 移向 next 的位置；
• 重复操作直至 cur 移动到链表末尾；
• 最后让 cur 指向 last，然后将 last 移向 链表的末尾位置并返回；
• 时间复杂度：O(n)。

• 利用递归函数的特点先反转头节点之后的所有节点；
• 例如：1 -> 2 -> 3 -> 4 -> 5 通过 reverseList(head.next) 可以得到 1 -> (5 -> 4 -> 3 -> 2) ；
• 然后利用head.next.next = head 将头节点加入链表的反转部分的尾部；
• 最后将 head.next 置为 null 即可。

class Solution {
    ListNode reverseList(ListNode head) {
        ListNode last = null;
        ListNode cur = head;
        if(cur == null) return last;
        while(cur.next != null) {
            ListNode next = cur.next;
            cur.next = last;
            last = cur;
            cur = next;
        }
        cur.next = last;
        last = cur;
        return last;    
    }
};

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}