剑指 Offer 24. 反转链表

剑指 Offer 24. 反转链表

题目：

• 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

• 示例:

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

• 限制：

0 <= 节点个数 <= 5000
1

思路：

• 方法一：双指针法，从前到后逐个修改指针
• 第一步：初始化指针，curr 指向 head ，表示当前结点，pre 表示当前结点的前驱结点，刚开始指向null
• 第二步：循环修改指针，直到curr当前结点为null
  • 先记录curr的next节点，防止后序修改丢失
  • 修改curr指向前一个结点
  • 移动pre结点到当前curr结点
  • 移动curr结点到下一个结点
• 最后，pre指向的为原链表最后一个结点，即现在的头结点

class Solution {
    public ListNode reverseList(ListNode head) {
		//初始化指针
        ListNode curr = head, pre = null;

        while(curr != null) {
            //先记录curr的next节点，防止丢失
            ListNode tmp = curr.next;
            //修改curr指向前一个结点
            curr.next = pre;
            //移动pre结点到当前curr结点
            pre = curr;
            //移动curr结点到下一个结点
            curr = tmp;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 方法二：递归，在回溯时修改指针指向
• 第一步：定义递归函数，传入curr当前结点 和 pre 前驱结点
• 第二步：递归函数中要做的事情：
  • 寻找next结点直到最后一个
  • 在回溯时修改指针指向
  • 最后返回头结点就可以啦

class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);
    }
    
    private ListNode recur(ListNode curr, ListNode pre) {
        // 终止条件
        if (curr == null) return pre;
        //递归，寻找最后节点
        ListNode res = recur(curr.next, curr);
        //在回溯时修改指针指向
        curr.next = pre;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

OVER~