leetcode：138. 随机链表的复制

二、思路

本题是给出一个单链表，单链表的每个结点还额外有一个随机指针，随机指向其他结点，要求复制该链表。

常规情况下复制链表，只需要遍历原链表，新建和原链表相同的结点尾插到新链表即可。

但是该链表有一个随机指针，还需要找到原链表中各个结点随机指针的指向，让新链表中结点的随机指针也指向新链表中的与原链表中相同位置的结点。因此还要在新链表中找到原链表中各个结点随机指针指向的结点，算法为O(N^2)，且判断是否为随机指针指向的结点只能通过结点值判断，如果链表中有多个值相同的结点，九不便于判断是否为随机指针指向的结点。

 

上述方法不易实现，此处提供一个全新的思路：

由于新建一个链表每个结点的随机指针不好复制，那么就在原链表上复制每个结点，然后再复制每个结点的随机指针。

先在原链表每个结点后复制一个相同的结点，复制完成后，再次遍历链表，就可以通过当前结点随机指针指向结点的下一个结点找到复制结点随机指针需要指向的结点。最后将每个复制的结点从原链表中拆下来，重新链接组成新的链表即可完成链表的复制。

三、代码

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node*cur=head;
	while(cur)//在原链表每个结点后复制一个相同的结点
	{
		struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
		copy->val=cur->val;
		copy->next=cur->next;
		cur->next=copy;

		cur=cur->next->next;
	}

	cur=head;
	while(cur)
	{
		//复制结点的随机指针指向的结点就是当前结点随机指针指向结点的下一结点
		if(cur->random)
			cur->next->random=cur->random->next;
		else
			cur->next->random=NULL;

		cur=cur->next->next;
	}

	cur=head;
	struct Node* newhead=NULL;
	struct Node *tail=NULL;
	while(cur)//拆下复制的结点并恢复原链表，重新链接这些结点
	{
		struct Node* next=cur->next;
		cur->next=next->next;
		if(tail==NULL)
		{
			newhead=tail=next;
		}
		else
		{
			tail->next=next;
			tail=next;
		}
		cur=cur->next;
	}

	return newhead;

}