? ? ? ? 學完了單鏈表之后，我們對其基本結(jié)構(gòu)已經(jīng)有了一定的了解，接下來我們通過一些題目強化對鏈表的理解，同時學習一些面試筆試題目的新思路以及加強對數(shù)據(jù)結(jié)構(gòu)單鏈表的掌握。?
目錄
題目一.876. 鏈表的中間結(jié)點 - 力扣（LeetCode）
題目二：21. 合并兩個有序鏈表 - 力扣（LeetCode）
題目三：203. 移除鏈表元素 - 力扣（LeetCode）
題目四：?206. 反轉(zhuǎn)鏈表 - 力扣（LeetCode）
題目五：141. 環(huán)形鏈表 - 力扣（LeetCode）
題目六：?142. 環(huán)形鏈表 II - 力扣（LeetCode）
題目一.876. 鏈表的中間結(jié)點 - 力扣（LeetCode）
- 給你單鏈表的頭結(jié)點?
head?，請你找出并返回鏈表的中間結(jié)點。 - 如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。
我們一起來思考一下這道題目：返回鏈表的中間結(jié)點。我們先來了解一種新思路：快慢指針！我們定義兩個指針：一個快指針，一個慢指針。每次快指針走兩步，慢指針走一步。我們來看一下演示過程：
一個中間結(jié)點情況：
兩個中間結(jié)點情況：
通過演示過程我們可以清楚的看到：
- 如果是奇數(shù)結(jié)點，當fast指向尾結(jié)點，slow返回中間結(jié)點。
- 如果是偶數(shù)結(jié)點，當fast指向空時（越過尾結(jié)點），slow返回中間結(jié)點。
總結(jié)以上規(guī)律，應(yīng)在當 fast遇到或越過尾節(jié)點時跳出循環(huán)，并返回?slow?即可。
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow=head,*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}題目二：21. 合并兩個有序鏈表 - 力扣（LeetCode）
- 將兩個升序鏈表合并為一個新的?升序?鏈表并返回。
- 新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
我們要返回一個升序的新鏈表，那么我們可以借助一個頭指針，將list1和list2進行比較，值小的尾插放入新的鏈表中，再用頭指針指向新的鏈表就可以。
在題目中注意判斷l(xiāng)ist1為空，list2為空是怎么辦？
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode*head=NULL,*tail=NULL;
// 處理特殊情況
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
while(list1&&list2)
{
if(list1->val<list2->val)
{
if(tail==NULL)
tail=head=list1;
else
{
tail->next=list1;
tail=tail->next;
}
list1=list1->next;
}
else
{
if(tail==NULL)
tail=head=list2;
else
{
tail->next=list2;
tail=tail->next;
}
list2=list2->next;
}
}
if(list1)
tail->next=list1;
if(list2)
tail->next=list2;
return head;
}題目三：203. 移除鏈表元素 - 力扣（LeetCode）
給你一個鏈表的頭節(jié)點?head?和一個整數(shù)?val?，請你刪除鏈表中所有滿足?Node.val == val?的節(jié)點，并返回?新的頭節(jié)點?。
思路一：我們定義一個指針，讓這個指針移動從而去尋找鏈表中和val相等的值，要是遇到就把它釋放掉，然后把上一個結(jié)點和釋放掉后的下一個結(jié)點連接起來，最后返回頭結(jié)點head就可以。但這個思路有什么問題我們想一想？如果頭結(jié)點就需要釋放呢，那我們就要把返回的頭結(jié)點此時后移，注意考慮這個情況！
大家可以自己思考一下，再參考下面代碼。
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode*prev=NULL,*cur=head;
while(cur)
{
if(cur->val==val)
{
if(cur==head)
{
head=cur->next;
free(cur);
cur=head;//cur=head->next錯誤
}
else
{
prev->next=cur->next;
free(cur);
cur=prev->next;
}
}
else
{
prev=cur;
cur=cur->next;
}
}
return head;
}思路二：我們定義一個新的結(jié)點，當指針指向的值不等于val值的時候，把結(jié)點連接到新結(jié)點上。這樣返回的新的頭結(jié)點就是一個沒有val值的鏈表。
大家可以自己思考一下，再參考下面代碼。
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* cur=head;
struct ListNode* tail=NULL,*newnode=NULL;
while(cur)
{
if(cur->val==val)
{
struct ListNode* node=cur;
cur=cur->next;
free(node);
}
else
{
if(tail==NULL)
{
newnode=tail=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}
cur=cur->next;
}
}
if(tail)
tail->next=NULL;
return newnode;
}題目四：?206. 反轉(zhuǎn)鏈表 - 力扣（LeetCode）
給你單鏈表的頭節(jié)點?head?，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
還記得之前寫的線性表頭插嗎？我們發(fā)現(xiàn)頭插和輸入的順序剛好相反，那我們把這個思想用在這道題目上，我們把鏈表的值頭插到新的一個鏈表中，返回頭插后的鏈表的頭結(jié)點。
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* cur=head;
struct ListNode* newhead=NULL;
while(cur)
{
struct ListNode* next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}題目五：141. 環(huán)形鏈表 - 力扣（LeetCode）
- 給你一個鏈表的頭節(jié)點?
head?，判斷鏈表中是否有環(huán)。 - 如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤?
next?指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數(shù)進行傳遞?。僅僅是為了標識鏈表的實際情況。 -
如果鏈表中存在環(huán)?，則返回?
true?。 否則，返回?false?。
這個題目超級有意思，檢查鏈表里有沒有環(huán)，還記得我們的快慢指針嗎？如果有環(huán)的話，快指針肯定先入環(huán)，慢指針如果在環(huán)中和快指針相遇了，說明有環(huán)；如果沒有相遇，說明無環(huán)。
大家肯定有一個問題：為什么有環(huán)就一定可以追上，我們一起分析一下。當slow進環(huán)后，fast開始追擊，假設(shè)它們之間的距離為N，那么走一次，它們之間的距離變?yōu)镹-1，下一次為N-2，N-3,......3，2，1，0，最后它們之間的距離就是0。所以只要有環(huán)，它們一定會相遇。
bool hasCycle(struct ListNode *head) {
struct ListNode* slow=head,*fast=head;
while(fast&&fast->next)//快指針將到達鏈表尾部，該鏈表不為環(huán)形鏈表
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}題目六：?142. 環(huán)形鏈表 II - 力扣（LeetCode）
- 給定一個鏈表的頭節(jié)點 ?
head?，返回鏈表開始入環(huán)的第一個節(jié)點。?如果鏈表無環(huán)，則返回?null。 - 如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤?
next?指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環(huán)。注意：pos?不作為參數(shù)進行傳遞，僅僅是為了標識鏈表的實際情況。
這個題目其實有點數(shù)學題的意思，我們來分析一下：假設(shè)起點到入口點的距離是L，環(huán)的周長是C，入口點到相遇點距離是X，我們已經(jīng)分析過，slow進環(huán)后一圈內(nèi)，fast必追上slow，那么slow的距離就是：L+X，fast的距離是L+n*C+X，L可能很長，導致fast已經(jīng)在環(huán)里走路不止一圈，slow才進入，所以fast是n*C，那么我們已知fast走的距離是slow的兩倍，這是快慢指針的定義，所以我們列出式子：2（L+X）=L+n*C+X，解出L=（n-1)*C+C-X.也就是說，一個指針從起點走，另一個從相遇點走，他們會在入口點相遇。
文章來源：http://www.zghlxwxcb.cn/news/detail-756668.html
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow,*fast;
slow=fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
struct ListNode* meet=slow;
while(head!=meet)
{
meet=meet->next;
head=head->next;
}
return meet;
}
}
return NULL;
}今天的分享就到這里，大家有哪里不懂的可以私信我，或在評論區(qū)討論，大家可以把這些題目作為鏈表的練習題目，希望對大家的編程和數(shù)據(jù)結(jié)構(gòu)有幫助！?文章來源地址http://www.zghlxwxcb.cn/news/detail-756668.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——圖解鏈表OJ題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
