算法篇-面試必刷Top1-反轉連結清單

BM1 反轉連結清單

描述

給定一個單連結清單的頭結點pHead(該頭節點是有值的，比如在下圖，它的val是1)，長度為n，反轉該連結清單後，傳回新連結清單的表頭。

資料範圍：

0 ≤ n ≤ 1000 0\leq n\leq1000 0≤n≤1000

要求：空間複雜度O(1) ，時間複雜度 O(n) 。

如當輸傳入連結表{1,2,3}時，

經反轉後，原連結清單變為{3,2,1}，是以對應的輸出為{3,2,1}。

以上轉換過程如下圖所示：

解題思路：

疊代，從頭掃一遍連結清單

将連結清單反轉，就是将每個表元的指針從向後變成向前，那我們可以周遊原始連結清單，将遇到的節點的指針一一逆向即可。指針怎麼逆向，不過是斷掉目前節點向後的指針，改為向前罷了。

具體做法：

• step 1：優先處理空連結清單，空連結清單不需要反轉。
• step 2：我們可以設定兩個指針，一個目前節點的指針，一個上一個節點的指針（初始為空）。
• step 3：周遊整個連結清單，每到一個節點，斷開目前節點與後面節點的指針，并用臨時變量記錄後一個節點，然後目前節點指向上一個節點，即可以将指針逆向。
• step 4：再輪換目前指針與上一個指針，讓它們進入下一個節點及下一個節點的前序節點。

Python代碼

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # 處理空連結清單
        if not head:
            return None
        cur = head # 指向目前節點
        pre = None # 指向目前節點的上一個節點
        while cur: # 當節點不為空時，即連結清單沒掃完
            # 斷開連結清單，要記錄後一個
            temp = cur.next
            # 目前的後繼指向前一個
            cur.next = pre
            # pre更新為目前
            pre = cur
            # 目前更新為剛剛記錄的後一個
            cur = temp
        return pre
           

C++代碼

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //處理空連結清單
        if(pHead == NULL)
            return NULL;
        ListNode* cur = pHead;
        ListNode* pre = NULL;
        while(cur != NULL){
            //斷開連結清單，要記錄後續一個
            ListNode* temp = cur->next; 
            //目前的next指向前一個
            cur->next = pre; 
            //前一個更新為目前
            pre = cur; 
            //目前更新為剛剛記錄的後一個
            cur = temp; 
        }
        return pre;
    }
};