codeMario

逆风赶路，不负众望

剑指 Offer 24.反转链表

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

示例

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

题解

反转链表可以用迭代（双指针）或递归两种方法实现

方法一：迭代（双指针）

总体思想是遍历链表，在访问各节点时修改next引用指向。

时间复杂度： 遍历链表使用线性大小时间为O(N)。

空间复杂度： 变量 pre 和 cur 使用常数大小额外空间为O(1)。

  1. 分别初始化cur、pre，分别指向头结点和null。

image-20220620214702035

  1. 链表指向是单向的，在改变当前节点指向并指向前序节点pre时，当前节点cur和后续节点之间的指向会断开，为了避免这种情况，我们需要在改变节点指向之前设置tmp值将cur的后续节点保存下来。

    image-20220620220138711

  2. 暂存当前节点，并访问下一个节点。

    image-20220620220423973

  3. tmp保存cur的后续节点。

    image-20220620220535284

  4. 以下操作同上~~，最终得到以下结果

    image-20220620220739273

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while(cur != nullptr) {
            ListNode* tmp = cur->next; // 暂存后继节点 cur.next
            cur->next = pre;           // 修改 next 引用指向
            pre = cur;                 // pre 暂存 cur
            cur = tmp;                 // cur 访问下一节点
        }
        return pre;
    }
};

方法二：递归

​ 使用递归的方法去遍历链表，当越过尾节点后终止递归，在回溯时候修改各节点next引用指向。

需要注意以下几点：

  • 在recur(cur, pre) 递归函数中，当 cur 为空，则返回尾节点pre（即反转链表的头节点）
  • 递归后继节点，记录返回值（即反转链表的头节点）为 res
  • 修改当前节点 cur引用指向前驱节点pre；
  • 返回反转链表的头节点res；

时间复杂度： 遍历链表使用线性大小时间为 O(N) 。
空间复杂度 ： 遍历链表的递归深度达到N ，系统使用额外空间大小为O(N) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recur(head, nullptr);           // 调用递归并返回
    }
private:
    ListNode* recur(ListNode* cur, ListNode* pre) {
        if (cur == nullptr) return pre;        // 终止条件
        ListNode* res = recur(cur->next, cur); // 递归后继节点
        cur->next = pre;                       // 修改节点引用指向
        return res;                            // 返回反转链表的头节点
    }
};
LeetCode LeetCodelinked list