剑指 Offer 24. 反转链表

难度 简单

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

示例:

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

限制：

1
0 <= 节点个数 <= 5000

1.迭代（双指针）

考虑遍历链表，并在访问各节点时修改 next 引用指向，算法流程见注释。

复杂度分析：
时间复杂度 O(N)O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(1)O(1) ： 变量 pre 和 cur 使用常数大小额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur,*pre,*tmp;
        pre = NULL;
        cur = head;
        while(pre)
        {
            tmp = cur->next;    // 暂存后继节点 cur.next
            cur->next = pre;    // 修改 next 引用指向
            pre = cur;            // pre 暂存 cur
            cur = tmp;            // cur 访问下一节点
        }
        return pre;
    }
};

2.递归

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

recur(cur, pre)递归函数：
终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）；
递归后继节点，记录返回值（即反转链表的头节点）为 res ；
修改当前节点 cur 引用指向前驱节点 pre ；
返回反转链表的头节点 res ；
reverseList(head) 函数：
调用并返回 recur(head, null) 。传入 null 是因为反转链表后， head 节点指向 null ；

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;                            // 返回反转链表的头节点
    }
};

剑指 Offer 35. 复杂链表的复制

难度 中等

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

img

1
2
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

img

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

示例 3：

img

1
2
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

1
2
3
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000 。

注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

迭代+结点拆分

第一次遍历：在链表各节点中间插入新的节点，复制节点的值

第二次遍历：复制链表各节点的random指向

第三次遍历：分离链表，将两个链表之间的next关系分离形成两个链表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        Node *headNew, *cur, *Pre;
        Pre = head;
        while(Pre != NULL)
        {
            cur = (Node*)malloc(sizeof(Node));
            cur->val = Pre->val;
            cur->next = Pre->next;
            Pre->next = cur;
            Pre = Pre->next->next;
        }
        cur = head;
        while(cur)
        {
            if(cur->random!=NULL) cur->next->random = cur->random->next;
            else cur->next->random = NULL;
            cur = cur->next->next;
        }
        headNew = head->next;cur = head->next;Pre = head;  
        while(Pre)
        {
            Pre->next = cur->next;
            Pre = Pre->next;
            if(cur->next!=NULL) cur->next = Pre->next;
            cur = cur->next;
        }
        return headNew;
    }
};