剑指 Offer(第2版)面试题 35:复杂链表的复制
剑指 Offer(第2版)面试题 35:复杂链表的复制
题目来源:
48. 复杂链表的复刻
解法1:模拟
算法:
-
复制原始链表的节点 N 并创建新节点 N’,把 N’ 链接到 N 的后面。
-
设置复制节点的 random 指针。
-
拆分链表:把奇数位置的节点链接起来就是原始链表,把偶数位置的节点链接起来就是复制链表,最后返回复制链表的头节点。
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 是原始链表的节点个数。算法创建了每个节点的副本。