終于學會反轉連結清單了｜leetcode206、nc78（cpp、java實作）

前期提要：

連結清單反轉是高頻考點，在各大高頻題排名網站長期占領前三，在牛客網穩居第一。

連結清單反轉之是以很重要，是因為它在實際程式設計中應用廣泛，可以解決很多與連結清單相關的問題。一些算法和資料結構需要借助連結清單來實作，比如LRU緩存淘汰算法、資料結構棧和隊列等等。而連結清單的反轉是其中一個最基本的操作，通過反轉可以使得連結清單的周遊順序與原來相反，這樣就可以更友善實作一些算法和問題的解決。同時，連結清單反轉也是一道經典的面試題，掌握連結清單反轉的方法可以幫助程式員在面試中獲得更好的表現。

題目來源：牛客nc78；力扣leetcode206

本題有兩種方法，帶頭結點和不帶頭結點，由不帶頭結點又可以引申出第三種方法——遞歸。

方法一：虛拟節點法（頭插法）

1. 首先，建立一個虛拟節點，并将其指向原連結清單的頭節點，讓我們稱之為dummy節點。這樣做的好處是，無論頭節點是否為null，我們都可以在dummy節點上進行操作。
2. 接着，定義兩個指針，一個指向目前節點（curNode），一個指向目前節點的前一個節點（prevNode）。
3. 然後，我們開始周遊整個連結清單。每次疊代中，我們将curNode的next指向prevNode，然後将prevNode和curNode都向後移動一個位置。
4. 繼續循環直到curNode變為null，周遊完成。
5. 最後，讓dummy節點指向prevNode，即完成了連結清單的反轉。記得釋放dummy節點哦～

【在代碼中我們用ans來代表dummy（虛拟）節點】

C++中的虛拟節點（Virtual Node）通常指的是在連結清單或樹等資料結構中，為了簡化操作或者提升性能而添加的一個額外節點。虛拟節點并不存儲實際的資料，它隻是作為輔助節點存在。

在連結清單中，虛拟節點可以用來簡化插入和删除操作。通常連結清單的頭節點是特殊處理的，因為需要記錄連結清單的起始位置。如果沒有虛拟節點，插入和删除操作就需要單獨處理頭節點的情況。而有了虛拟節點，頭節點和其他節點的處理方式就一緻了，操作起來更加簡潔。

在樹中，虛拟節點可以用來處理邊界情況。例如，在二叉搜尋樹中，如果要插入一個新節點，但樹為空，那麼可以将新節點作為虛拟節點插入，并将其作為根節點。這樣可以避免在處理空樹時需要特殊處理的情況。

總的來說，虛拟節點是一種在資料結構中添加一個額外節點來簡化操作或處理邊界情況的技術。它并不存儲實際資料，隻起到輔助作用。

cpp複制代碼/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
         ListNode *ans=new ListNode(-1);
         ListNode *cur=head;
         while(cur!=nullptr){
             ListNode *next=cur->next;
             cur->next=ans->next;
             ans->next=cur;
             cur=next;
         }
         return ans->next;
    }
};
           

java複制代碼/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode ans=new ListNode(-1);
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=ans.next;
            ans.next=cur;
            cur=next;
        }
        return ans.next;
    }
}
           

不過這種方法可能會被面試官禁止，因為不借助虛拟結點的方式更難，更能考察面試者的能力。

方法二：雙指針疊代法

直接操作連結清單實作反轉

1. 首先定義兩個指針pre和cur，初始化時pre=head，cur=head.next；
2. 周遊連結清單，每次将cur指向的節點插入到pre之後，即cur.next=pre；
3. 操作完成後，将pre和cur往後移動一個節點，即pre=cur，cur=cur.next；
4. 重複步驟2和步驟3，直到cur為空，此時pre所指的節點為反轉後的連結清單頭，傳回pre即可。

直接修改，要注意設兩個指針

cpp複制代碼/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *currNode=head,*preNode=nullptr;
        while(currNode!=nullptr){
            ListNode *next=currNode->next;
            currNode->next=preNode;
            preNode=currNode;
            currNode=next;           
        }
        return preNode;
    }
};
           

java複制代碼/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode p1=null,p2=head;//p1為pre，p2為cur
        while(p2!=null){
            ListNode next=p2.next;
            p2.next=p1;
            p1=p2;
            p2=next;
        }
        return p1;
    }
}
           

我寫的時候雖然用對了雙指針，用對了判斷條件，但是忽略了ListNode *next=currNode->next;這一步。

為什麼ListNode *next=currNode->next;不可缺少？

因為在反轉連結清單的過程中，我們需要保留目前節點的下一個節點的引用，以便後續的周遊。如果缺少了這一步，我們将無法繼續周遊連結清單并對每個節點進行反轉操作。

将上面這段代碼在了解的基礎上背下來，因為這個算法太重要

方法三：遞歸

1. 當連結清單為空或隻有一個節點時，直接傳回該連結清單；
2. 用遞歸反轉除第一個節點之外的連結清單，傳回新的頭節點newHead；
3. 将第一個節點head連接配接到newHead之後，形成新的頭節點；
4. 傳回新的頭節點。

java複制代碼public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
    return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
           

cpp複制代碼struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode* newHead = reverseList(head->next);

    head->next->next = head;
    head->next = NULL;

    return newHead;
}
           

擴充題型

反轉連結清單是一道經典的算法題，它需要我們将連結清單中的節點順序完全颠倒過來。除了常見的反轉連結清單外，還有一些類似的題型，比如：

1. 反轉連結清單：将連結清單的節點順序完全颠倒過來；（lLeetCode206）
2. 反轉連結清單的一部分：将連結清單中指定區間的節點順序完全颠倒過來；（LeetCode92）
3. 每k個節點反轉連結清單：将連結清單中每k個節點的順序進行反轉；
4. K個一組反轉連結清單：将連結清單按照每k個節點一組進行反轉，不滿k個節點不做處理；（LeetCode25）
5. 反轉每對相鄰節點：将連結清單中每對相鄰節點的順序進行反轉。（LeetCode24）

作者：染落林間色

連結：https://juejin.cn/post/7260385528869322807