剑指 Offer（第2版）面试题 35：复杂链表的复制

剑指 Offer（第2版）面试题 35：复杂链表的复制

题目来源：48. 复杂链表的复刻

解法1：模拟

算法：

1. 复制原始链表的节点 N 并创建新节点 N’，把 N’ 链接到 N 的后面。
2. 设置复制节点的 random 指针。
3. 拆分链表：把奇数位置的节点链接起来就是原始链表，把偶数位置的节点链接起来就是复制链表，最后返回复制链表的头节点。

PS：少有的书上代码比其他解法要好的，推荐书上解法，拆分成三步走，清晰明了。

代码：

/*** Definition for singly-linked list with a random pointer.* struct ListNode {*     int val;*     ListNode *next, *random;*     ListNode(int x) : val(x), next(NULL), random(NULL) {}* };*/
class Solution
{
public:ListNode *copyRandomList(ListNode *head){CloneListNodes(head);SetRandomPointer(head);return SplitList(head);}// 第一步：复制原始链表的节点 N 并创建新节点 N'，把 N' 链接到 N 的后面void CloneListNodes(ListNode *head){ListNode *p = head;while (p){// 复制节点ListNode *clone = new ListNode(0);clone->val = p->val;clone->next = p->next;clone->random = nullptr;p->next = clone;p = clone->next;}}// 第二步：设置复制节点的 random 指针void SetRandomPointer(ListNode *head){// 如果原始链表上的节点 N 的 random 指针指向 S，// 则它的复制节点 N' 的 random 指针指向 S'ListNode *p = head;while (p){ListNode *clone = p->next;if (p->random)clone->random = p->random->next;p = clone->next;}}// 第三步：拆分链表ListNode *SplitList(ListNode *head){ListNode *p = head;ListNode *cloneListHead = nullptr;ListNode *clone = nullptr;if (p){cloneListHead = p->next;clone = p->next;p->next = clone->next;p = p->next;}while (p){clone->next = p->next;clone = clone->next;p->next = clone->next;p = p->next;}return cloneListHead;}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是原始链表的节点个数。算法遍历了每个节点。

空间复杂度：O(n)，其中 n 是原始链表的节点个数。算法创建了每个节点的副本。