快捷導(dǎo)航

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

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

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

題目：

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

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

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

返回復(fù)制鏈表的頭節(jié)點(diǎn)。

struct Node {

int val;

struct Node *next;

struct Node *random;

};

思路：

因?yàn)槊總€(gè)節(jié)點(diǎn)還有一個(gè)隨機(jī)指針，向拷貝標(biāo)準(zhǔn)單向鏈表的方式才處理，是有困難的；

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

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

第二步，處理隨機(jī)指針，因?yàn)榭截惖木驮谠?jié)點(diǎn)后面，拷貝的隨機(jī)指針就指向原節(jié)點(diǎn)隨機(jī)指針的后一個(gè)；

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

第三步，將鏈表分開(kāi)，并返回拷貝鏈表的頭；

程序：

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

您可能感興趣的文章: