复杂链表的复制

题目链接

---

思路

如果不考虑random指针的复制，仅仅复制单链表的结构还是简单的。只需要通过一个指针cur遍历原链表，再不断创建新节点尾插到newHead后即可。

但如果要考虑random指针的复制，那过程就复杂了。

有小伙伴会这样想：既然原链表和复制的链表的结构一致，那么对于原链表的任意一个节点，我们都可以先知道它们random指针的指向，这样就可以通过循环得到这是原链表的第几个节点，最后也就可以通过循环将复制链表的相同节点的random指针指向相同的位置了。但是对于每一个节点，每确定一个random指针时间复杂度就是O(N)，一共N个节点时间复杂度就是O(N^2)，显然效率不高。

接下来给大家讲解一个时间复杂度为O(N)，空间复杂度为O(1)的方法：

• 第一步：新建节点，复制链表的val值、next值

  这里我们不采用新建一个头newHead，然后将新建的节点尾插到newHead后的方法。

  这里我们利用交织链表的方法：cur遍历原链表，每遍历一个节点就将复制的节点插入到这个节点之后。形象一点来说就是，如果原链表为A->B->C->NULL，那么这一步过后，链表就变成了A->A'->B->B'->C->C'->NULL

struct Node* cur = head;//先创建交织链表
while (cur)
{struct Node* temp = (struct Node*)malloc(sizeof(struct Node));temp->val = cur->val;temp->next = cur->next;cur->next = temp;cur = cur->next->next;
}

• 第二步：完成random指针的复制

  实现了上面交织链表的操作，我们就可以直接得到复制链表的节点的random指着的指向了：

  即为其原节点 S 的随机指针指向的节点 T 的后继节点 T'。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。

  通过下图也可以理解对应的关系：

​

//复制random指针
cur = head;while (cur)
{struct Node* temp = cur->random;    //找到随机指针的指向if (temp == NULL)cur->next->random = NULL;elsecur->next->random = temp->next;cur = cur->next->next;
}

• 最后一步，将交织的链表拆成两串链表，返回复制链表的头

  虽然我们也可以不对原链表进行还原，但安全起见，最好不要改变原有的链表结构

struct Node* retHead = head->next;	//要返回的头节点
struct Node* cur1 = head;
struct Node* cur2 = retHead;//取消交织，还原为两个链表
while (cur1 && cur2->next)
{cur1->next = cur1->next->next;cur2->next = cur2->next->next;cur1 = cur1->next;cur2 = cur2->next;
}cur1->next = NULL;
cur2->next = NULL;//最后返回复制链表
return retHead;

实现代码

struct Node* copyRandomList(struct Node* head) {if (head == NULL)return NULL;struct Node* cur = head;//先创建交织链表while (cur){struct Node* temp = (struct Node*)malloc(sizeof(struct Node));temp->val = cur->val;temp->next = cur->next;cur->next = temp;cur = cur->next->next;}//复制随机指针cur = head;while (cur){struct Node* temp = cur->random;    //找到随机指针的指向if (temp == NULL)cur->next->random = NULL;elsecur->next->random = temp->next;cur = cur->next->next;}//取消交织struct Node* retHead = head->next;	//要返回的头节点struct Node* cur1 = head;struct Node* cur2 = retHead;//取消交织，还原为两个链表while (cur1 && cur2->next){cur1->next = cur1->next->next;cur2->next = cur2->next->next;cur1 = cur1->next;cur2 = cur2->next;}cur1->next = NULL;cur2->next = NULL;//最后返回复制链表return retHead;
}