[剑指 Offer 24] 反转链表

[剑指 Offer 24]反转链表

题目

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

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

题解

• 方法一：双指针迭代修改next指向
  • 让当前结点指向头结点，当前结点的前一个节点初始为空
  • 当前结点不等于null时，循环遍历链表
  • 循环中改变next指针的指向
  • 注意：在修改next指针指向时，先要临时保存当前的下一个结点，防止链表丢失

public ListNode reverseList(ListNode head) {

        ListNode cur = head, pre = null;

        while(cur != null) {
            ListNode tmp = cur.next; // 临时存放cur.next
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12

• 方法二：利用递归回溯修改next指向
  • 递归终止条件：当前结点为空返回
  • 递归：一直递归到最后一个不为null的节点，然后开始回溯修改next指向

public ListNode reverseList(ListNode head) {
         return recur(head, null);
     }

     private ListNode recur(ListNode cur, ListNode pre) {

         if (cur == null) return pre;

         ListNode res = recur(cur.next, cur); //递归调用
         cur.next = pre;  // 修改节点引用指向
         return res;
     }
1
2
3
4
5
6
7
8
9
10
11
12

反转链表反转链表反转链表

---