歡迎來到我的：世界

該文章收入欄目：鏈表

希望作者的文章對你有所幫助，有不足的地方還請指正，大家一起學習交流 !

---

前言

---

對于我來說這個博客是一個學習的地方，就像我的上篇文章一樣，有老鐵們的支持，陪伴；我很滿足，這個欄目我會繼續堅持下去，108回，就像我的108難一樣，只要撐過磨難，一定能取到真經；

--------------------------對過程全力以赴，對結果淡然處之

---

第一題：反轉一個鏈表

---

地址：oj地址

---

解題思路：

思路：讓鏈表翻轉過來，可以先創造一個新的鏈表頭指針指向空，然后原來的鏈表一個一個頭插到新的指針，到時候在返回新創造的鏈表起始位置。按照這個思路；

我們需要創造一個新指針變量指向空：

然后接下來就是將原鏈表頭插入newnode；

這里需要注意一下：如果按照頭插入newnode,如果指針pHead將結點插入來的話，那pHead原指向的下一個結點就丟失了，所以這里需要創造一個新的指針 next 存放pHead所指的下一個結點，這樣才能找回去；

后面步驟依次將后續頭插入；這里有一步也需要注意，記得讓cur找回到next的結點，然后使next再指向cur下一個結點；

直到pHead為空結束，最后返回newnode；

代碼：

struct ListNode* ReverseList(struct ListNode* head ) {// write code herestruct ListNode* newnode = NULL;struct ListNode* cur = head;//頭插while (cur) {//為了cur能夠找回下一個結點struct ListNode* next = cur->next;//頭插cur->next = newnode;newnode = cur;//cur指針找回到下一個結點cur = next;}return newnode;
}

---

第二題：鏈表內指定區間反轉

---

地址：oj地址

---

加強版的反轉鏈表；

思路：
先利用cur指針指向該鏈表 head 的位置，依次往下找,直到遇到要反轉區間的起始位置，ret指針記錄住該位置 (后面鏈接起來的要用到);在讓cur往下走，這里應該注意要用prve指針判斷在原來鏈表是否有結點，是否有節點關系到后面鏈接時的方式（是head，還是prve->next）這點很重要；然后從cur現在位置開始進行頭插（為了反轉給區間鏈表）到一個新鏈表newnode，直到走到區間的末尾都頭插入后(包括了末尾這個結點);之后就是鏈接的步驟，需要將head和newnode鏈接起來所以這里用到了prve進行判斷；
具體的更詳細在下面細講：

在這里我想著重想解釋一下為什么要設置prve：

這里來舉兩個測試用例

第一個：這種相當于第二種情況：

創造cur指針指向的是head，prve先是指向空，開始找區間起始位置，根據m值(m為2，則應該找第二個結點)，每找過一個節點，將cur給到prve(這是為了判斷區別出是不是從頭就開始頭插，在后面鏈接時會用來判斷其鏈接的方式，在上面有詳細解釋)，直到找到區間起始(如果m=1，則直接從第一個進行頭插，這個時候的prve仍指向空)，在這個位置設置ret，下面進行依次頭插入；

直到區間所有頭插完：

最后進行鏈接起來，讓prve->next 指向newnode ，ret->next指向cur，最后返回head；

還有一個測試用例：

這就相當于的是情況1：
全部進行了反轉：

全部頭插完后，將head指向newnode，

代碼實現：

#include <math.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {// write code hereif (head == NULL || head->next == NULL || m == n)return head;struct ListNode* cur = head;struct ListNode* newnode = NULL, * tail = NULL;newnode = (struct ListNode*)malloc(sizeof(struct ListNode));newnode->next = tail = NULL;//找到m的最后一個int count=m;struct ListNode*prev=NULL;while(count-->1){prev=cur;cur=cur->next;}struct ListNode*ret=cur;//進行頭插反轉int len=n-m+1;while(len--){struct ListNode*next=cur->next;cur->next=newnode->next;newnode->next=cur;cur=next;}//鏈接if(prev==NULL){head=newnode->next;ret->next=cur;}else {prev->next=newnode->next;ret->next=cur;}
return head;
}

---

第三題：判斷一個鏈表是否為回文結構

---

地址：oj地址

---

• 首先我們要知道什么是回文結構：
• 如

偶數回文：1 2 2 1
奇數回文：1 2 3 2 1

解題思路：

思路：找到中間的結點，然后讓中間結點后的所有節點反轉，然后，返回的這個中間節點 rever 與該鏈表的第一個結點進行依次比較值，相等就完后走，直到指向中間的這個節點 rever 指向空；

這里會用到返回中間結點的這個函數；和反轉一串鏈表函數(就是本篇文章的第一題)；這兩個我們之前已經寫過了：老鐵們可以去看看：返回中間結點;

代碼：

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;}//反轉一串鏈表并返回該鏈表的頭地址struct ListNode* ReverseList(struct ListNode* head ) {// write code herestruct ListNode* newnode=NULL;struct ListNode* cur = head;while (cur) {struct ListNode* next = cur->next;//頭插cur->next = newnode;newnode = cur;cur = next;}return newnode;}//實現判斷是否為回文結構
bool isPail(struct ListNode* head ) {// write code herestruct ListNode* mid = middleNode(head);struct ListNode* rever = ReverseList(mid);while (rever) {if (head->val != rever->val) {return false;}rever = rever->next;head = head->next;}return true;
}

總結

---

對每到題，可能還是可以優化的，如果還有更好的方法的老鐵，可以在評論區里面一起進行討論哦，在后面隨著小孩的知識儲備越多，小孩肯定還會加以優化優化！！

---

到了最后：感謝支持

我還想告訴你的是：
------------對過程全力以赴，對結果淡然處之
也是對我自己講的