C語言數據結構之復雜鏈表的拷貝

Posted on by

題目：

給你一個長度為 n 的鏈表，每個節點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節點或空節點。

構造這個鏈表的 深拷貝。 深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的 next 指針和 random 指針也都應指向復制鏈表中的新節點，並使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態。復制鏈表中的指針都不應指向原鏈表中的節點 。

例如，如果原鏈表中有 X 和 Y 兩個節點，其中 X.random –> Y 。那麼在復制鏈表中對應的兩個節點 x 和 y ，同樣有 x.random –> y 。

返回復制鏈表的頭節點。

struct Node {

int val;

struct Node *next;

struct Node *random;

};

思路：

因為每個節點還有一個隨機指針，向拷貝標準單向鏈表的方式才處理，是有困難的；

第一步，先將拷貝的節點鏈在原節點後面

    struct Node* cur = head;
	while (cur)
	{
		struct Node* new = (struct Node*)malloc(sizeof(struct Node));
		new->val = cur->val;
 
		new->next = cur->next;
		cur->next = new;
 
		cur = new->next;
	}

第二步，處理隨機指針，因為拷貝的就在原節點後面，拷貝的隨機指針就指向原節點隨機指針的後一個；

    struct Node* cur = head;    
    while (cur)
	{
		struct Node* copy = cur->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}
		cur = copy->next;
	}

第三步，將鏈表分開，並返回拷貝鏈表的頭；

程序：

struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
	{
		return NULL;
	}
	struct Node* cur = head;
	while (cur)
	{
		struct Node* new = (struct Node*)malloc(sizeof(struct Node));
		new->val = cur->val;
 
		new->next = cur->next;
		cur->next = new;
 
		cur = new->next;
	}
 
	cur = head;
	
	while (cur)
	{
		struct Node* copy = cur->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}
		cur = copy->next;
	}
 
	cur = head;
	struct Node* copyHead = head->next ,*copy_n=copyHead->next,*copy=copyHead;
	while (cur)
	{
		if (copy_n == NULL)
		{
			copy->next = NULL;
			cur->next = NULL;
			return copyHead;
		}
		else
		{
			cur->next = copy_n;
			copy->next = copy_n->next;
		}
		cur = copy_n;
		copy = copy_n->next;
		copy_n = copy->next;
	}
	return copyHead;
}

到此這篇關於C語言數據結構之復雜鏈表的拷貝的文章就介紹到這瞭,更多相關C語言 數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：