快捷導航

C語言數(shù)據(jù)結(jié)構(gòu)之復雜鏈表的拷貝

更新時間：2021年11月03日 14:23:46 作者：i_Crave

復雜鏈表指的是一個鏈表有若干個結(jié)點，每個結(jié)點有一個數(shù)據(jù)域用于存放數(shù)據(jù)，還有兩個指針域，其中一個指向下一個節(jié)點，還有一個隨機指向當前復雜鏈表中的任意一個節(jié)點或者是一個空結(jié)點。今天我們要實現(xiàn)的就是對這樣一個復雜鏈表復制產(chǎn)生一個新的復雜鏈表

題目：

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

構(gòu)造這個鏈表的深拷貝。深拷貝應(yīng)該正好由 n 個全新節(jié)點組成，其中每個新節(jié)點的值都設(shè)為其對應(yīng)的原節(jié)點的值。新節(jié)點的 next 指針和 random 指針也都應(yīng)指向復制鏈表中的新節(jié)點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。復制鏈表中的指針都不應(yīng)指向原鏈表中的節(jié)點。

例如，如果原鏈表中有 X 和 Y 兩個節(jié)點，其中 X.random --> Y 。那么在復制鏈表中對應(yīng)的兩個節(jié)點 x 和 y ，同樣有 x.random --> y 。

返回復制鏈表的頭節(jié)點。

struct Node {

int val;

struct Node *next;

struct Node *random;

};

思路：

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

第一步，先將拷貝的節(jié)點鏈在原節(jié)點后面

    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;
	}

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

    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;
}

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之復雜鏈表的拷貝的文章就介紹到這了,更多相關(guān)C語言數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: