C 鏈表

飄渺o40uv5vs24 2023-02-13 發(fā)布于陜西

展開全文

鏈表結(jié)構(gòu)

一,，單鏈表

1.實(shí)現(xiàn)基本的增刪查改

2.對鏈表進(jìn)行一些操作

（1）刪除等于給定值的所有節(jié)點(diǎn)。

（2）翻轉(zhuǎn)鏈表

（3）返回中間節(jié)點(diǎn)的地址

（4）倒數(shù)第k個節(jié)點(diǎn)

雖然C++中有l(wèi)ist容器,，但是在某些oj題中會出現(xiàn)有關(guān)鏈表的題，所以寫一篇C++鏈表,。

省去太過官方的定義,，只做最簡單易懂的介紹。

鏈表結(jié)構(gòu)

一個數(shù)據(jù)所在的內(nèi)存塊被分為兩個部分,，第一個部分放數(shù)據(jù),，而第二個部分則放下一個數(shù)據(jù)的地址，以此來連接各個數(shù)據(jù),，最后一個內(nèi)存塊放的地址為NULL,。這樣的一個內(nèi)存塊叫做節(jié)點(diǎn)。

在代碼中,，鏈表的一個節(jié)點(diǎn)是這樣的：


struct ListNode
{
	int data;
	ListNode* next;//結(jié)構(gòu)體指針
};

鏈表有一定的缺陷：每存放一個數(shù)據(jù)都需要伴隨下一個數(shù)據(jù)的地址并且不支持隨機(jī)訪問,。

一，單鏈表

先來看最簡單的單鏈表,。

1.實(shí)現(xiàn)基本的增刪查改


#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//結(jié)構(gòu)體指針
};
void Listprintf(ListNode* phead)
{
	ListNode* cur=phead;
	while (cur != NULL)
	{
		cout << cur->data << '->';
		cur = cur->next;
	}
}
void Listpushback(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		ListNode* tail=  *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void test_1()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3); 
	Listprintf(phead);
}
int main()
{
	test_1();
	return 0;
}

運(yùn)行結(jié)果：

在這段代碼中有一些需要注意的地方,，比如：

在Listpushback這個函數(shù)中，參數(shù)是二級指針,，如果寫成一級指針：


void Listpushback(ListNode* pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (pphead == NULL)
	{
		pphead = newnode;
	}
	else
	{
		ListNode* tail=  pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

則結(jié)果會變成：

沒有任何輸出,。

原因是原本的指針phead是沒有任何指向的,，這個指針沒有指向某一個地址，而是一個空指針,，在函數(shù)傳參的時候,，如果參數(shù)pphead是一級指針，則pphead也是空指針,，改變pphead,，并不會影響到phead，所以最終一通操作下來,，phead還是空指針,，輸出結(jié)果也就是空的。

下面再增加一些功能：


#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//結(jié)構(gòu)體指針
};
void Listprintf(ListNode* phead)
{
	ListNode* cur=phead;
	while (cur != NULL)
	{
		cout << cur->data << '->';
		cur = cur->next;
	}
	cout << 'NULL' << endl;
}
//尾插
void Listpushback(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		ListNode* tail=  *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
//頭插
void Listpushfront(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾刪
void Listpopback(ListNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	if ((*pphead)->next == NULL)
	{
		delete(*pphead);
		*pphead = NULL;
	}
	else
	{
		ListNode* tail = *pphead;
		ListNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		delete(tail);
		tail = NULL;
		prev->next = NULL;
	}
}
//頭刪
void Listpopfront(ListNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		ListNode* newnode = (*pphead)->next;
		delete(*pphead);
		*pphead = newnode;
	}
}
//查找元素,，返回值是地址
ListNode* Listfind(ListNode* phead, int x)
{
	ListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
//插入元素,，在pos的前一個位置插入
//配合Listfind使用，具體使用見test_insert函數(shù)
void Listinsert(ListNode** phead, ListNode* pos, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*phead == pos)
	{
		newnode->next = (*phead);
		*phead = newnode;
	}
	else
	{
		ListNode* posprev = *phead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		posprev->next = newnode;
		newnode->next = pos;
	}
}
//單鏈表并不適合在前一個位置插入,，因?yàn)檫\(yùn)算較麻煩,，會損失效率
//包括c++中為單鏈表提供的庫函數(shù)也只有一個insert_after而沒有前一個位置插入
//在后一個位置插入相對簡單
void Listinsert_after(ListNode** phead, ListNode* pos, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	newnode->next = pos->next;
	pos->next = newnode;
}
//刪除指定位置的節(jié)點(diǎn)
void Listerase(ListNode** pphead, ListNode* pos)
{
	if (*pphead == pos)
	{
		*pphead = pos->next;
		delete(pos);
	}
	else
	{
		ListNode* prev = *pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		delete(pos);
	}
}
//釋放鏈表
void Listdestory(ListNode** pphead)
{
	ListNode* cur = *pphead;
	while(cur)
	{
		ListNode* next = cur->next;
		delete(cur);
		cur = next;
	}
	*pphead = NULL;
}
void test_insert()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	ListNode* pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		Listinsert(&phead, pos, 20);
	}
	Listprintf(phead);
	pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		Listinsert_after(&phead, pos, 20);
	}
	Listprintf(phead);
	Listdestory(&phead);
}
void test_find()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	ListNode* pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		pos->data = 20;//Listfind不僅能查找，也能借此修改,，這也是函數(shù)返回地址的原因
	}
	Listprintf(phead);
	Listdestory(&phead);
}
void test_erase()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	ListNode* pos = Listfind(phead, 2);
	if (pos != NULL)
	{
		Listerase(&phead, pos);
	}
	Listprintf(phead);
	Listdestory(&phead);
}
void test_pop_and_push()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	Listprintf(phead);
	Listpushfront(&phead, 1);
	Listpushfront(&phead, 2);
	Listpushfront(&phead, 3);
	Listprintf(phead);
	Listpopback(&phead);
	Listpopfront(&phead);
	Listprintf(phead);
	Listdestory(&phead);
}
int main()
{
	//test_pop_and_push();
	test_find();
	//test_insert();
	//test_erase();
	return 0;
}

test_pop_and_push()測試結(jié)果：

test_find()測試結(jié)果：

test_insert()測試結(jié)果：

test_erase()測試結(jié)果：

2.對鏈表進(jìn)行一些操作

（1）刪除等于給定值的所有節(jié)點(diǎn),。

例如：在一條鏈表中刪除值為6的節(jié)點(diǎn)。


#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//結(jié)構(gòu)體指針
};
void Listprintf(ListNode* phead)
{
	ListNode* cur=phead;
	while (cur != NULL)
	{
		cout << cur->data << '->';
		cur = cur->next;
	}
	cout << 'NULL' << endl;
}
void Listpushback(ListNode** pphead, int x)
{
	ListNode* newnode = new ListNode{ x,NULL };
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		ListNode* tail=  *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
ListNode* creatlist()
{
	ListNode* phead = NULL;
	Listpushback(&phead, 1);
	Listpushback(&phead, 9);
	Listpushback(&phead, 6);
	Listpushback(&phead, 8);
	Listpushback(&phead, 6);
	Listpushback(&phead, 2);
	Listpushback(&phead, 3);
	return phead;
}
ListNode* removeElements(ListNode* head, int x)
{
	ListNode* prev = NULL;
	ListNode* cur = head;
	while (cur)
	{
		if (cur->data == x)
		{
			if (cur == head)//如果第一個元素就是要刪除的,，進(jìn)行頭刪
			{
				head = cur->next;
				delete(cur);
				cur = head;
			}
			else
			{
				prev->next = cur->next;
				delete(cur);
				cur = prev->next;
			}
		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;
}
int main()
{
	ListNode*phead = creatlist();//先創(chuàng)建一條鏈表
	Listprintf(phead);
	phead = removeElements(phead, 6);//刪除值為6的節(jié)點(diǎn)
	Listprintf(phead);
	return 0;
}

自測結(jié)果：

當(dāng)然如果是一條全為6的鏈表也是可以完成刪除的：

這里再說一下為什么刪除元素和創(chuàng)建鏈表這兩個函數(shù)的參數(shù)不是二級指針,，因?yàn)檫@兩個函數(shù)是要返回一個指針的。

（2）翻轉(zhuǎn)鏈表

比如：將1->2->3->4->5翻轉(zhuǎn)為5->4->3->2->1

翻轉(zhuǎn)鏈表的方式很多,，這里只寫兩種作為參考：

第一種,，翻轉(zhuǎn)指針。

這種方法的邏輯是定義三個指針,，一個用來紀(jì)錄當(dāng)前位置的前一個位置,，一個用來紀(jì)錄當(dāng)前位置，一個用來紀(jì)錄當(dāng)前位置的后一個位置,，再通過將當(dāng)前位置指向下一個位置的指針修改為指向上一個位置,，再往后迭代，以達(dá)到翻轉(zhuǎn)鏈表的目的,。

為什么要三個指針呢,，因?yàn)閷?dāng)前位置指向前一個位置之后，就找不到當(dāng)前位置的下一個位置了,，所以需要第三個指針來指向下一個位置,。

代碼部分由于只有測試函數(shù)不一樣，其余代碼差異不大,，所以僅貼出測試函數(shù)部分：


ListNode* reverseList(ListNode* head)
{
	if (head == NULL)
	{
		return NULL;
	}
	ListNode* prev, * cur, * next;
	prev = NULL;
	cur = head;
	next = cur->next;
	while (cur)
	{
		cur->next = prev;//翻轉(zhuǎn)指針
		//往后迭代
		prev = cur;
		cur = next;
		if (next)//這里是因?yàn)楫?dāng)cur指向最后一個節(jié)點(diǎn)的時候,，next就已經(jīng)是NULL了，這個時候如果再執(zhí)行next=next->next則會出現(xiàn)錯誤
		{
			next = next->next;
		}
	}
	return prev;
}

自測結(jié)果：

測試結(jié)果（測試網(wǎng)站：?？途W(wǎng)）：

第二種方式,，創(chuàng)建新鏈表進(jìn)行頭插

這種方法的邏輯是將原鏈表中的節(jié)點(diǎn)取下來頭插到新鏈表newlist中，同樣的,，需要三個指針,，一個為NULL，即為新鏈表newlist,，一個紀(jì)錄原鏈表從頭開始的地址,，一個紀(jì)錄下一個位置。將原鏈表第一個節(jié)點(diǎn)取下來對newlist進(jìn)行頭插,，再取第二個第三個,，往后迭代。


ListNode* reverseList(ListNode* head)
{
	ListNode* cur = head;
	ListNode* newlist = NULL;
	ListNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		//頭插
		cur->next = newlist;
		newlist = cur;
		//往后迭代
		cur = next;
	}
	return newlist;
}

自測結(jié)果：

測試結(jié)果（測試網(wǎng)站：?？途W(wǎng)）：

（3）返回中間節(jié)點(diǎn)的地址

如果有兩個中間節(jié)點(diǎn),，返回第二個中間節(jié)點(diǎn)。

這種操作比較簡單,，最容易想到的方法就是先遍歷一次整個鏈表找出有幾個節(jié)點(diǎn),，再遍歷一次找出中間節(jié)點(diǎn)

但是如果要求只能遍歷一次呢，所以這里不采用遍歷兩次的方法,，而采用快慢指針的方式只遍歷一次,。

邏輯就是定義兩個指針，一個走的更慢,，一次走一步,，另一個走的更快，一次走兩步,。


ListNode* middleNode(ListNode* head)
{
	ListNode* slow, * fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

自測結(jié)果：

（4）倒數(shù)第k個節(jié)點(diǎn)

輸入一個鏈表和k,，輸出從倒數(shù)第k個節(jié)點(diǎn)到最后一個。

思路和快慢指針相似,，定義兩個指針,，一個指針先走k步。


ListNode* findK(ListNode* head, int k)
{
	ListNode* fast, * slow;
	fast = slow = head;
	while(k--)
	{
		if (fast == NULL)//如果當(dāng)fast等于NULL時k仍不為0,，則k大于鏈表長度
		{
			return NULL;
		}
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

自測結(jié)果：

測試結(jié)果（測試網(wǎng)站：?？途W(wǎng)）：

（5）合并有序鏈表

思路比較簡單，依次比較鏈表中的節(jié)點(diǎn),，將較小的節(jié)點(diǎn)尾插到新鏈表,。

當(dāng)然還有一種做法是將一個鏈表直接插入到另一個鏈表中，這種方式畫圖畫起來倒是簡單,，但是實(shí)際寫起來很麻煩,，這里不推薦這種寫法,，也不會寫這種。


ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{
	if (l1 == NULL)//如果一個鏈表為空,，則返回另一個
	{
		return l2;
	}
	if (l2 == NULL)
	{
		return l1;
	}
	ListNode* head = NULL;
	ListNode* tail = NULL;
	while (l1 && l2)
	{
		if (l1->data < l2->data)
		{
			if (head == NULL)
			{
				head = tail =l1;
			}
			else
			{
				tail->next = l1;
				tail = l1;
			}
			l1 = l1->next;
		}
		else
		{
			if (head == NULL)
			{
				head = tail = l2;
			}
			else
			{
				tail->next = l2;
				tail = l2;
			}
			l2 = l2->next;
		}
	}
	if (l1)
	{
		tail->next = l1;
	}
	if(l2)
	{
		tail->next = l2;
	}
	return head;
}

自測結(jié)果：

我這里是將兩條1->2->3->4->5->6的鏈表合并,。

測試結(jié)果（測試網(wǎng)站：牛客網(wǎng)）：

可以看到這種不帶哨兵位的寫法也還是比較麻煩,，要判斷頭為不為空,，所以下面再寫一種帶哨兵位的寫法。

帶哨兵位（也叫帶頭）就是我們?nèi)ソo鏈表多定義一個頭結(jié)點(diǎn),，這個節(jié)點(diǎn)不存儲有效數(shù)據(jù),。


ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{
	if (l1 == NULL)//如果一個鏈表為空，則返回另一個
	{
		return l2;
	}
	if (l2 == NULL)
	{
		return l1;
	}
	ListNode* head = NULL, * tail = NULL;
	head = tail = new ListNode;//哨兵位的頭結(jié)點(diǎn)
	while (l1 && l2)
	{
		if (l1->data < l2->data)
		{
		    tail->next = l1;
		    tail = l1;
		    l1 = l1->next;
	 	}
		else
		{
			tail->next = l2;
			tail = l2;
			l2 = l2->next;
		}
	}
	if (l1)
	{
		tail->next = l1;
	}
	if (l2)
	{
		tail->next = l2;
	}
	ListNode* list = head->next;
	delete(head);
	return list;
}

自測結(jié)果：

測試結(jié)果（測試網(wǎng)站：?？途W(wǎng)）：

（6）分割鏈表

給定一個值x,，將所有小于x的節(jié)點(diǎn)排在其余節(jié)點(diǎn)之前，且不能改變原來的數(shù)據(jù)順序,，返回重新排列后的鏈表頭指針,。

思路：定義兩條鏈表，一條將小于x的所有節(jié)點(diǎn)按照原順序連接成鏈表,，另一條將大于x的所有節(jié)點(diǎn)按照原順序連接成鏈表,，最后再合起來。


ListNode* partition(ListNode* phead, int x)
{
	ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
	lesshead = lesstail = new ListNode;//定義一個哨兵位頭結(jié)點(diǎn),，方便尾插
	lesstail->next = NULL;
	greaterhead = greatertail = new ListNode;
	greatertail->next = NULL;
	ListNode* cur = phead;
	while (cur)
	{
		if (cur->data < x)
		{
			lesstail->next = cur;
			lesstail = cur;
		}
		else
		{
			greatertail->next = cur;
			greatertail = cur;
		}
		cur = cur->next;
	}
	lesstail->next = greaterhead->next;
	greatertail->next = NULL;//舉個例子,，這樣一條鏈表:1->4->15->5,現(xiàn)在給的x是6，那么排序后15應(yīng)該在最后,，正因如此,，重新排序后15的next是沒變的，仍然指向5,，不手動將next改為NULL,，就會成環(huán)，無限排下去,。
	ListNode* newhead = lesshead->next;
	delete(lesshead);
	delete(greaterhead);
	return newhead;
}

自測結(jié)果：

測試結(jié)果（測試網(wǎng)站：力扣）：

（7）鏈表回文

判斷鏈表是否回文,。

思路，先找到一條鏈表的中點(diǎn),，將后半段逆置,，設(shè)置兩個指針，一個從頭開始,，一個從逆置后的頭開始,，逐個判斷直到最后。

圖：

節(jié)點(diǎn)奇數(shù)個：

節(jié)點(diǎn)偶數(shù)個：

代碼：


ListNode* middleNode(ListNode* head)
{
	ListNode* slow, * fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}
ListNode* reverseList(ListNode* head)
{
	ListNode* cur = head;
	ListNode* newlist = NULL;
	ListNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		//頭插
		cur->next = newlist;
		newlist = cur;
		//往后迭代
		cur = next;
	}
	return newlist;
}
bool check(ListNode* head)
{
	ListNode* mid = middleNode(head);
	ListNode* rhead = reverseList(mid);
	ListNode* curHead = head;
	ListNode* curRhead = rhead;
	while(curHead&&curRhead)
	{
		if (curHead->data != curRhead->data)
			return false;
		else
		{
			curHead = curHead->next;
			curRhead = curRhead->next;
		}
	}
	return true;
}

自測結(jié)果：

測試結(jié)果（測試網(wǎng)站：?？途W(wǎng)）：

（8）鏈表相交

給兩個單鏈表的頭結(jié)點(diǎn),，找出并返回兩個單鏈表相交的起始節(jié)點(diǎn),，沒有交點(diǎn)則返回null。

最簡單粗暴的思路就是將A鏈表的每個節(jié)點(diǎn)和B鏈表的每個節(jié)點(diǎn)挨著挨著比較,，這里不使用這一種,。

還有一種思路就是，找到A和B的尾結(jié)點(diǎn)對比,，如果一樣則有交點(diǎn)，如果不一樣則沒有交點(diǎn),，有交點(diǎn)的情況下又該怎樣找到相交的起始節(jié)點(diǎn),？

如果兩條鏈表在相交之前的節(jié)點(diǎn)個數(shù)一樣的話，那么找到相交的起始節(jié)點(diǎn)就很簡單,，定義兩個指針同時向前走直到相等即可,，所以我們在找鏈表A和B的尾結(jié)點(diǎn)的時候，同時紀(jì)錄下A和B的長度,，用長的減去短的得到一個數(shù)x,，再分別為兩條鏈表定義頭指針，讓長的那條鏈表的頭指針先走x步,，那么就可以當(dāng)做是在相交之前節(jié)點(diǎn)數(shù)一樣了,。


ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
{
        if(pHead1==NULL)
        {
            return NULL;
        }
        if(pHead2==NULL)
        {
            return NULL;
        }
        ListNode* tail1=pHead1;
        ListNode* tail2=pHead2;
        int len1=1,len2=1;
        while(tail1->next)
        {
            len1++;
            tail1=tail1->next;
        }
        while(tail2->next)
        {
            len2++;
            tail2=tail2->next;
        }
        if(tail1!=tail2)//不相交
        {
            return NULL;
        }
        int gap=abs(len1-len2);
        ListNode* longlist=pHead1;
        ListNode* shortlist=pHead2;
        if(len1<len2)
        {
            longlist=pHead2;
            shortlist=pHead1;
        }
        while(gap--)//長的先走差距步，再同時走找交點(diǎn)
        {
            longlist=longlist->next;
        }
        while(longlist!=shortlist)
        {
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
        return longlist;
    }

測試結(jié)果（測試網(wǎng)站：?？途W(wǎng)）：

（9）環(huán)形鏈表

判斷鏈表是否帶環(huán),，并且返回環(huán)的入口節(jié)點(diǎn)。

判斷是否帶環(huán)的思路比較簡單,，定義兩個指針,，一個走得快，一次走兩步,，一個走得慢,，一次走一步，如果不帶環(huán),，那么走得快的最終會走到NULL,，如果帶環(huán)，那么走得快的會和走得慢的相遇,。

要找環(huán)的入口節(jié)點(diǎn),，也需要定義兩個指針，一個從鏈表頭開始,，一個從快慢指針相遇的位置開始,，他們同時出發(fā)，當(dāng)這兩個指針相遇時,，所在的位置就是入口節(jié)點(diǎn),。

這里做簡單的證明,，假設(shè)鏈表頭到入口節(jié)點(diǎn)距離是L，快慢指針相遇的位置meetnode距離入口節(jié)點(diǎn)為x

假設(shè)C是環(huán)的長度,，當(dāng)快慢指針相遇時,，快指針走的距離是L+N*C+x，N是快指針走的圈數(shù),，慢指針走的距離是L+x,，因?yàn)榭熘羔樢淮巫邇刹剑羔樢淮巫咭徊?，所以快指針走的距離是慢指針的兩倍,，所以有：

L+N*C+x=2（L+x）

得到：

L+x=N*C

L=（N-1）*C+C-x

其中C-x即為meetnode到入口節(jié)點(diǎn)的距離，所以當(dāng)頭指針和從meetnode出發(fā)的指針相遇時,，頭指針走了L,，從meetnode出發(fā)的指針走了C-x，相遇點(diǎn)即為入口節(jié)點(diǎn),。

代碼：


ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode*fast=pHead;
        ListNode*slow=pHead;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(fast==slow)
            {
                ListNode*meet=fast;
                while(meet!=pHead)
                {
                    meet=meet->next;
                    pHead=pHead->next;
                }
                return pHead;
            }
        }
        return NULL;
    }

測試結(jié)果（測試網(wǎng)站：?？途W(wǎng)）：

這里再說下還有另一種處理方式，就是將meetnode作為鏈表的尾,，meetnode的next作為鏈表的頭,，就轉(zhuǎn)化成了兩條相交鏈表找第一個相交節(jié)點(diǎn)的問題，這種方式寫起來會麻煩一些,，這里也不做代碼實(shí)現(xiàn),。

二，雙向鏈表

雙向鏈表的一個數(shù)據(jù)所在的內(nèi)存塊是被分成了三部分,，除了像單鏈表那樣一部分存儲數(shù)據(jù),，一部分存儲下一個數(shù)據(jù)的地址之外，還要有一部分來存儲上一個數(shù)據(jù)的地址,。

在代碼中如下：


struct ListNode
{
	int data;
	ListNode* next;//結(jié)構(gòu)體指針
	ListNode* prev;
};

雙向鏈表的結(jié)構(gòu)：

其中最常用的是雙向帶頭（哨兵位）循環(huán)鏈表

后面的代碼中雙向鏈表也都是這種,。

1.增刪查改

這里多說一句，很多人都會下意識的認(rèn)為在帶哨兵位的鏈表中,，哨兵位是一條鏈表開始的位置,，但是實(shí)際上哨兵位的下一位才是。


#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
	int data;
	ListNode* next;//結(jié)構(gòu)體指針
	ListNode* prev;
};
ListNode* Initlist()//初始化雙向帶頭（哨兵）循環(huán)鏈表
{
	ListNode* phead=new ListNode;
	phead->next = phead;
	phead->prev = phead;//定義一個哨兵位,，自己的next和prev指向自己
	return phead;
}
void pushback(ListNode* phead,int x)//尾插
{
	ListNode* tail = phead->prev;//循環(huán)鏈表,，哨兵位的前一個就是尾
	ListNode* newhead = new ListNode;
	newhead->data = x;
	newhead->next = phead;
	newhead->prev = tail;
	tail->next = newhead;
	phead->prev = newhead;
}
void popback(ListNode* phead)//尾刪
{
	if (phead->next == phead)//鏈表為空，不能再刪了
		return;
	ListNode* tail = phead->prev;
	ListNode* tailprev = tail->prev;
	tailprev->next = phead;
	phead->prev = tailprev;
	delete(tail);
}
void pushfront(ListNode* phead,int x)//頭插
{
	ListNode* next = phead->next;
	ListNode* newnode = new ListNode;
	newnode->data = x;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}
void popfront(ListNode* phead)//頭刪
{
	if (phead->next == phead)//鏈表為空,，不能再刪了
		return;
	ListNode* next = phead->next;
	ListNode* dnext = next->next;
	phead->next = dnext;
	dnext->prev = phead;
	delete(next);
}
ListNode* listFind(ListNode* phead, int x)//查找
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
void insertList(ListNode* pos, int x)//指定位置插入
{
	ListNode* prev = pos->prev;
	ListNode* newnode = new ListNode;
	newnode->data = x;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
void eraseList(ListNode* pos)//指定位置刪除
{
	ListNode* posNext = pos->next;
	ListNode* posPrev = pos->prev;
	posNext->prev = posPrev;
	posPrev->next = posNext;
	delete(pos);
	pos = NULL;
}
void printlist(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		cout << cur->data << ' ';
		cur = cur->next;
	}
	cout << endl;
}
void test_pop_push()
{
	ListNode* phead = Initlist();
	pushback(phead, 1);
	pushback(phead, 2);
	pushback(phead, 3);
	printlist(phead);
	popback(phead);
	popback(phead);
	printlist(phead);
	pushfront(phead, 1);
	pushfront(phead, 2);
	pushfront(phead, 3);
	printlist(phead);
	popfront(phead);
	popfront(phead);
	printlist(phead);
}
void test_find_insert_erase()
{
	ListNode* phead = Initlist();
	pushback(phead, 1);
	pushback(phead, 2);
	pushback(phead, 3);
	printlist(phead);
	ListNode* p = listFind(phead, 2);
	insertList(p, 20);
	printlist(phead);
	p = listFind(phead, 20);
	eraseList(p);
	printlist(phead);
}
int main()
{
	//test_pop_push();
	test_find_insert_erase();
	return 0;
}

test_pop_push()測試結(jié)果：

test_find_insert_erase()測試結(jié)果：

其中最重要的是insert()和erase()函數(shù),，在雙向帶頭循環(huán)鏈表中，這兩個函數(shù)是可以分別和頭尾插，頭尾刪函數(shù)復(fù)用的,，即可以修改成：


void pushback(ListNode* phead,int x)//尾插
{
	insertList(phead,x);
}
void popback(ListNode* phead)//尾刪
{
	if (phead->next == phead)//鏈表為空,，不能再刪了
		return;
	eraseList(phead->prev);
}
void pushfront(ListNode* phead,int x)//頭插
{
	insertList(phead->next, x);
}
void popfront(ListNode* phead)//頭刪
{
	if (phead->next == phead)//鏈表為空，不能再刪了
		return;
	eraseList(phead->next);
}

最后再說一下為什么雙向鏈表中的函數(shù)的參數(shù)是一級指針而不是像之前單鏈表那樣是二級指針的問題 ,，這是因?yàn)樵谖覍懙碾p向鏈表中是帶了頭的,，也就是帶了哨兵位，所以不需要考慮傳進(jìn)來的是空指針,，改變形參不會影響變量的問題,，而在我寫單鏈表的時候是沒有帶頭的。

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間,，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購買等信息，謹(jǐn)防詐騙,。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請點(diǎn)擊一鍵舉報。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：飄渺o40uv5vs24 > 《待分類》

舉報/認(rèn)領(lǐng)