歡迎來到我的：世界
收錄專欄：鏈表
希望作者的文章對你有所幫助，有不足的地方還請指正，大家一起學習交流 !
目錄
- 前言
- 第一題：刪除鏈表的倒數第n個節點
- 第二題：鏈表的中間結點
- 第三題：合并兩個排序的鏈表
- 總結
前言
- 在這里寫的是有關鏈表的落坑題，詳細寫了我落坑的全過程，相信大家也都掉過坑，該專欄我會持續更新，感謝鐵子們的支持。
-———————對過程全力以赴，對結果淡然處之
第一題：刪除鏈表的倒數第n個節點
地址： oj題地址
解題思路：
- 1.暴力遍歷：
我們先遍歷一遍，找到該鏈表中有多少個節點(第一次遍歷)，然后再第二次遍歷找到倒數第n個節點，再進行刪除，再返回原地址。這種方法可以說是這道題的比較簡單的實現方法。再這里我想講一下另一種方法：
2.三指針法：
先創造三個指針，tail指針，sur指針，dst指針，而sur，dst指針一開始指向是鏈表的起始地址，tail指針是指向sur指針前一個字節的地址，這就需要重新開辟一塊空間其中的next 可以找到sur的地址；
起始時物理圖：
注意：鏈表因為地址不是相連的，其地址可以看作是隨機的，圖中的地址都是我隨便編的,只是為了方便更容易觀察思路：先讓dst指針向后走n個節點，這樣的話，dst指針和sur指針就相距了n個節點，然后讓這三個指針一起向后一次移動一個節點，直到dst指針指向空指針，這樣的話，sur所指的就是倒數第n個節點(這一步觀念很重要，一定要想清楚),這個時候有要刪除的那個節點地址，也有該節點上一個節點的地址tail指針所指，那就可以很好的完成刪除。
以上的是思路，下面來進行實現；結束時的物理圖：
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {// write code here//sur指針是指向要刪除的那個節點，dst是與sur保持間距n的，tail是sur前一個節點struct ListNode* sur = head, *dst = head;struct ListNode*tail =(struct ListNode*)malloc(sizeof(struct ListNode));tail->next=sur;//先讓dst指針走n個節點while (n--) {dst = dst->next;}while (dst) {//三個指針一起出發，tail指針始終指向sur指針前前一個節點 dst = dst->next;sur = sur->next;tail = tail->next;}//刪除if (head == sur) {//如果sur沒動說明要刪的就在第一個head = head->next;sur = head->next;} else {//要刪的只要找到sur指針的前一個節點，就可以讓sur后一個節點與之相連tail->next = sur->next;}return head;
}
第二題：鏈表的中間結點
地址：oj地址
解題思路：
- 1.暴力遍歷法：
根據這道題的正常思路，肯定是先遍歷一遍該鏈表的所有結點的個數，就可以得出中間點了，最后返回指向該點的地址；這種方法很尋常，在這里我就不具體講了，我想具體講下一種方法：- 2.快慢指針法：
該方法思路是：先設置兩個指針：slow，fast，分別是快慢指針，首先兩個指針都是指向鏈表的起始位置，slow向下一個結點移動，而fast向下兩個結點移動，直到fast指針停下，那fast指針什么時候停呢，肯定有不同情況，如果鏈表的結點時偶數時，這時fast 走到空為止，而如果鏈表總結點時奇數時,這時fast走到尾結點停下。
----如為奇數時：邏輯圖：
第一步：
第二步：
第三步
若為偶數時：
邏輯圖:
第一步：
第二步：
第三步：
第四步：
代碼：
struct ListNode* middleNode(struct ListNode* head ) {// write code here//設置快慢指針struct ListNode*sur=head,*dst=head;//當dst指針為空或dst指向的next為空就停下while(dst && dst->next){sur=sur->next;dst=dst->next->next;}return sur;
}
第三題：合并兩個排序的鏈表
地址：oj地址
解題思路：
首先鏈表和順序表不同，有些思路是行不通的；但也有其優點，鏈表是由一個一個結點連起來的，可以隨時拆下來的；
用歸并的方法，我們可以先創造兩個指針，讓需要歸并的兩組鏈表由起始位置進行比較，較小值尾插入一個指針，另一個指針是找到需要插入的前一個結點，好方便尾插；
比較1<2，尾插入 1 ，如果是第一次插入，應該先讓head指針和tail指針同時指向 1 的地址；如果不是第一次插入，那就是應該pHead1的地址給tail->next，然后讓tail指針指向tail->next，最后讓pHead1指向下一個結點；
- 然后是 2<3 ，尾插入2的地址；跟上面的步驟一樣；
注意：這里之后就不是第一次插入，記得讓tail指針指向tail的下一個結點；
后面的步驟幾乎是一樣的；
直到有一個鏈表沒有了，在將剩下鏈表直接進行尾插入，就可以了；
最后返回head指針；
但是這就對了么？
不是的，還有一步我們忘記了，如果兩個鏈表其中一個是空，那這個程序的結果肯定報錯，所以我們還要在最開始進行判斷，如果有其中一個為空，則直接返回另一個鏈表；
代碼：
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {// write code here//如果其中一個鏈表為空，則直接返回另一個鏈表if(pHead1==NULL)return pHead2;if(pHead2==NULL)return pHead1;struct ListNode* head = NULL, *tail = NULL;//判斷哪個鏈表先為空，就跳出去while (pHead1 && pHead2) {if (pHead1->val < pHead2->val) {if (tail == NULL) {//第一次尾插head = tail = pHead1;} else {//不是第一次尾插tail->next = pHead1;tail=tail->next;}//讓篇pHead1指針找到下一個結點pHead1 = pHead1->next;} else {if (tail == NULL) {//第一次尾插head = tail = pHead2;} else {//不是第一次尾插tail->next = pHead2;tail=tail->next;}//讓篇pHead2指針找到下一個結點pHead2 = pHead2->next;}}//判斷哪個鏈表先為空，然后讓另一個鏈表直接尾插入；
if(pHead1)tail->next=pHead1;if(pHead2)tail->next=pHead2;return head;
}
總結
在這里感謝老鐵們的觀看，在這里小孩謝謝大家的支持，以上的題目都是基于小孩現在的能力來說，如果還有更好的方法的老鐵，可以在評論區里面一起進行討論哦，在后面隨著小孩的知識儲備越多，小孩肯定還會加以優化優化！！
到了最后：
我還想告訴你：
------------對過程全力以赴，對結果淡然處之
也是對我自己講的
