鏈表反轉類演算法題

反轉鏈表類

NO1. 反轉鏈表

給定一個長度為 n 的鏈表，反轉該鏈表，輸出表頭。

方法一：迭代法（推薦使用）

演算法流程：

  • step 1 ：特殊情況判斷，空鏈表或只有一個結點的鏈表，直接返回頭結點；
  • step 2 ：設置兩個指針cur和prev，cur指向當前結點，prev指向上一個結點（初始為 null）；
  • step 3 ：遍歷整個鏈表，每到一個結點，斷開當前結點cur與下一個結點 cur.next 的指針，並用臨時變數 temp 記錄下一個結點，然後當前結點的next指向上一個結點（實現反轉）；
    • 輪換cur與上一個結點prev，進行下一個結點反轉；
    • 循環退出條件為 cur == null；
  • step 4 ：返回 prev（反轉後，原尾節點變成頭結點）；

程式碼實現：

public class Main {
    public ListNode ReverseList(ListNode head) {
        // 特殊情況判斷
		if(head == null || head.next == null) 	return head;
        // 雙指針
        ListNode prev = null, cur = head;
        while(cur != null) {
            ListNode temp = cur.next;	// 斷開鏈表，要記錄後續⼀個
            cur.next = prev;	// 當前的next指針指向前⼀個
            prev = cur;		// 前⼀個更新為當前
            cur = temp;		// 當前更新為剛剛記錄的後⼀個
        }
    }
}

複雜度分析：

  • 時間複雜度：\(O(N)\)，遍歷鏈表一次；
  • 空間複雜度：\(O(1)\)，申請常數個變數；

方法二：遞歸

根據迭代法，每當我們反轉鏈表中某個結點以後，要遍歷進入下一個結點進行反轉，相當於對後面的子鏈表進行反轉，那這就是一個子問題，因此我們可以使用遞歸來解決。

  • 終止條件：當到達鏈表尾部，要麼當前指針為空，要麼下一個指針為空，直接向上層返回當前結點；
  • 返回值：每一層向上一層返回翻轉後子問題的頭結點；
  • 本層任務：先進入後一個結點作為子問題，繼續反轉，然後記錄返回的頭結點，連接在本層結點的後面；

演算法流程：

  • step 1 ：遞歸向下遍歷鏈表，直到遍歷到最後一個結點；
  • step 2 ：往上一次逆轉兩個結點；
  • step 3 ：逆轉後的尾連接本層的結點 head，並斷開兩節點的原指針（置為 null）；

public class Main {
    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;
    }
}

複雜度分析：

  • 時間複雜度：\(O(N)\)，遍歷鏈表一次；
  • 空間複雜度：\(O(N)\)，遞歸棧的深度就是鏈表的長度\(N\)；

NO2. 鏈表內指定區間反轉

將一個結點為 size 的鏈表 m 位置到 n 位置之間的區間反轉；

鏈表其他部分不變，返回頭結點；

方法一：頭插法迭代（推薦）

第一步肯定是要先找到第 m 個位置，然後不斷反轉，直到到達 n 位置；由於m可能為1，即頭結點，那反轉之後 head 就不再指向頭結點了，所以，先構造一個虛擬頭結點；

演算法流程：

  • step 1 ：可以在鏈表頭添加一個虛擬頭結點，後續返回時去掉就好了；
  • step 2 ：使用兩個指針，cur指向當前結點，prev指向前驅節點；
  • step 3 ：依次遍歷鏈表，到達第 m 個位置；
  • step 4 ：從 m 到 n 位置的結點，依次斷掉指向下一個結點的指針，指向前驅，實現反轉；
  • step 5 ：返回虛擬頭結點的next；

程式碼實現：

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // 虛擬頭結點
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 雙指針（反轉鏈表常規操作）
        ListNode prev = dummy, cur = head;
        // 找到第 m 個結點
        for(int i = 1; i < m; i++) {
            prev = cur;
            cur = cur.next;
        }
        // cur 指向 m，開始反轉
        for(int i = m; i < n; i++) {
            ListNode tmp = cur.next;
            cur.next = tmp.next;	// 1
            tmp.next = pre.next;	// 2 開始頭插到 pre 後面
            pre.next = tmp;			// 3
        }
        return dummy.next;
    }
}

複雜度分析：

  • 時間複雜度：\(O(N)\)，最壞情況下，需要遍歷鏈表一次；
  • 空間複雜度：\(O(1)\)，申請常數個變數；

方法二：遞歸

演算法流程：

  • step 1 ：先利用遞歸找到反轉區間的起點；
  • step 2 ：再利用遞歸從第 n 個位置開始反轉，往上拼接；

程式碼實現：

public class Solution {    
	public ListNode reverseBetween (ListNode head, int m, int n) {
        // 找到第 m 個結點，執行反轉
        if(m == 1)    return reverse(head, n);
        // 找 第 m 個結點
        ListNode node = reverseBetween(head.next, m - 1, n - 1);
        head.next = node;	// 拼接已翻轉
        return head;
    }
    
    ListNode tmp = null;    // tmp用來暫存第n個結點的後繼
    public ListNode reverse(ListNode head, int n){
        // 遞歸停止
        if(n == 1) {
            tmp = head.next;
            return head;
        }
        ListNode node = reverse(head.next, n - 1);    //進⼊⼦問題
        head.next.next = head; //反轉
        head.next = tmp; //拼接
        return node;	// 返回上一層
    }
}

複雜度分析：

  • 時間複雜度：\(O(N)\)，最壞情況下，需要遍歷鏈表一次；
  • 空間複雜度：\(O(N)\)，最壞情況下，遞歸棧的深度就是鏈表的長度\(N\)；

NO.3 鏈表結點每K個一組翻轉

給定一個鏈表，從頭開始每 K 個作為一組，將每組的鏈表結點翻轉；

組與組之間的位置關係保持不變；

如果最後鏈表末尾剩餘不足 K 個結點，則不反轉，直接放在尾部；

方法一：頭插法迭代

演算法流程：

  • step 1 ：反轉過程中要改變 head 指針，就得設個虛擬頭結點，定義雙指針 pre和 cur；
  • step 2 ：統計鏈表總長度 len ，用於得出翻轉組數 len / k；
  • step 3 ：外循環控制翻轉組數，內循環控制組內的k個結點翻轉（頭插 k - 1次）

程式碼實現：

public class Main {
    public ListNode reverseKGroup (ListNode head, int k) {
        // 特判
        if(head == null || head.next == null || k < 2)	return head;
        // 要改變頭結點的，就得設個虛擬頭結點
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 雙指針，基本操作
        ListNode pre = dummy, cur = head;
        // 統計鏈表總長度
        int len = 0;
        ListNode p = head;
        while(p != null) {
            len++;
            p = p.next;
        }
        // 翻轉組數，僅翻轉 len / k
        for(int i = 0; i < len / k; i++) {
            // 外循環控制組數，內循環控制組內的k個結點翻轉（頭插 k - 1次）
            for(int j = 1; j < k; j++) {
                // 把一組內的結點 temp 頭插到 pre 後
                ListNode temp = cur.next;
                cur.next = temp.next;
                temp.next = cur;
                pre.next = temp;
            }
            // 一組翻轉完成，去下一組，
            pre = cur;		// pre 指向上一組尾結點 cur
            cur = cur.next;		// cur 指向下一組的第一個結點
        }
        return dummy.next;
    }
}

複雜度分析：

  • 時間複雜度：\(O(N)\)，需要遍歷鏈表兩次；
  • 空間複雜度：\(O(1)\)，申請常數個變數；

方法二：遞歸

終止條件：當進行到最後一個分組，元素個數不足 k 個，就將剩餘的最後一個分組直接返回給上層；

返回值：每一層要返回給上層的是翻轉後這個分組的頭結點，並且後面已經連接好了所有的已翻轉好的分組鏈表；

本層任務：先遍歷 k 次，找到該分組尾結點的位置，然後從分組的頭結點遍歷到尾結點，依次翻轉；

演算法流程：

  • step 1 ：翻轉前，找到每次分組的尾節點的下一個結點，即下一分組的頭結點
  • step 2 ：採用常規的翻轉鏈表操作；
  • step 3 ：遞歸進行拼接；

程式碼實現：

public class Main{
    public ListNode reverseKGroup (ListNode head, int k) {
        
        ListNode tail = head;
        // tail指向本組尾節點的下一個節點，即下一分組的頭結點
        for(int i = 0; i < k; i++) {
            // 最後一分組不足 k 個結點，直接向上層返回 head
            if(tail == null)	return head;
            tail = tail.next;
        }
        // 常規的翻轉鏈表操作
        ListNode pre = null, cur = head;
        while(cur != tail) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        // 當前尾指向下⼀段要翻轉的鏈表
        head.next = reverseKGroup(tail, k);
        // 
        return pre;
    }
}

複雜度分析：

  • 時間複雜度：\(O(N)\)，一共遍歷鏈表 n 個結點；
  • 空間複雜度：\(O(1)\)，申請常數個變數；

總結

鏈表反轉類演算法題，有兩種解決思路：

  1. 遍歷鏈表，利用兩個滾動指針，不斷改變當前結點的 next 指針的指向（當前結點的 next 指向前驅），每次改變指針時都要暫存下一個節點；
  2. 頭插法，每次把結點頭插到 prev 指針後，實現反轉；
Tags:

VirMach 便宜 VPS