在連結串列上實現 Partition 以及荷蘭國旗問題

作者：Grey

原文地址：

部落格園：在連結串列上實現 Partition 以及荷蘭國旗問題

CSDN：在連結串列上實現 Partition 以及荷蘭國旗問題

題目描述

給你一個連結串列的頭節點 head 和一個特定值 x ，請你對連結串列進行分隔，使得所有小於 x 的節點都出現在大於或等於 x 的節點之前。

你應當保留兩個分割區中每個節點的初始相對位置。

題目連結見：LeetCode 86. Partition List

主要思路

本題可以借鑑陣列的 Partition 操作，參考：荷蘭國旗問題與快速排序演演算法

Partition 操作就是荷蘭國旗的一種特殊情況而已。

我們可以把本題的難度稍微升級一下：如何在連結串列上實現荷蘭國旗問題？

第一種解法就是將連結串列先轉換成陣列，然後在陣列上實現荷蘭國旗問題，最後將陣列還原為連結串列並返回，該方法的時間複雜度是O(N)，空間複雜度是O(N)，不是最優解。

第二種解法是用有限幾個變數來實現，在同樣O(N)的時間複雜度的情況下，空間複雜度可以做到O(1)，設定如下幾個變數

ListNode sH = null; // 小於區域的頭結點
ListNode sT = null; // 小於區域的尾結點
ListNode eH = null; // 等於區域的頭結點
ListNode eT = null; // 等於區域的尾結點
ListNode mH = null; // 大於區域的頭結點
ListNode mT = null; // 大於區域的尾結點
ListNode next; // 記錄遍歷到的結點的下一個結點

接下來開始遍歷連結串列，進行主流程處理，虛擬碼如下

while (head != null) {
    next = head.next;
    // 如果head.val < pivot，則通過sH，sT構造小於區域的連結串列
    // 如果head.val == pivot，則通過eH，eT構造小於區域的連結串列
    // 如果head.val > pivot，則通過mH，mT構造小於區域的連結串列
    head = next;
}
// 把三個區域的連結串列串聯起來即可。

構造每個區域的連結串列的時候，還要考慮連結串列是第一次被構造還是已經構造了，以小於區域的連結串列為例，如果是第一次構造，則sH == null，此時需要把sH和sT同時初始化：

if (sH == null) {
    sH = head;
    sT = head;
}

如果不是第一次構造，則

sT.next = head;
sT = head;

開始區域的尾指標直接指向當前結點，然後把尾指標設定未當前結點即可。

其他兩個區域的連結串列處理方式同理。

最後需要把三個區域的連結串列連線起來：

        // 小於區域的尾巴，連等於區域的頭，等於區域的尾巴連大於區域的頭
        if (sT != null) { // 如果有小於區域
            sT.next = eH;
            eT = eT == null ? sT : eT; // 下一步，誰去連大於區域的頭，誰就變成eT
        }
        // all reconnect
        if (eT != null) { // 如果小於區域和等於區域，不是都沒有
            eT.next = mH;
        }
        // 如果小於區域有，小於區域的頭就是最終連結串列的頭
        // 如果小於區域沒有，等於區域的頭有，則等於區域的頭就是最終連結串列的頭
        // 如果小於和等於區域都沒有，則大於區域的頭就是最終連結串列的頭
        return sH != null ? sH : (eH != null ? eH : mH);

完整程式碼見

public class Code_PartitionList {

    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int data) {
            this.val = data;
        }
    }


    public static ListNode listPartition2(ListNode head, int pivot) {
        ListNode sH = null; // small head
        ListNode sT = null; // small tail
        ListNode eH = null; // equal head
        ListNode eT = null; // equal tail
        ListNode mH = null; // big head
        ListNode mT = null; // big tail
        ListNode next; // save next node
        // every node distributed to three lists
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.val < pivot) {
                if (sH == null) {
                    sH = head;
                    sT = head;
                } else {
                    sT.next = head;
                    sT = head;
                }
            } else if (head.val == pivot) {
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                if (mH == null) {
                    mH = head;
                    mT = head;
                } else {
                    mT.next = head;
                    mT = head;
                }
            }
            head = next;
        }
        // 小於區域的尾巴，連等於區域的頭，等於區域的尾巴連大於區域的頭
        if (sT != null) { // 如果有小於區域
            sT.next = eH;
            eT = eT == null ? sT : eT; // 下一步，誰去連大於區域的頭，誰就變成eT
        }
        // all reconnect
        if (eT != null) { // 如果小於區域和等於區域，不是都沒有
            eT.next = mH;
        }
        // 如果小於區域有，小於區域的頭就是最終連結串列的頭
        // 如果小於區域沒有，等於區域的頭有，則等於區域的頭就是最終連結串列的頭
        // 如果小於和等於區域都沒有，則大於區域的頭就是最終連結串列的頭
        return sH != null ? sH : (eH != null ? eH : mH);
    }
}

解決了連結串列的荷蘭國旗問題，那麼原題中的連結串列 Partition 問題，就迎刃而解了。

由於是 Partition，所以不存在等於區域，只需要考慮小於區域和大於區域，只需要設定如下幾個變數即可。

ListNode sH = null; // 小於區域的頭
ListNode sT = null; // 小於區域的尾
ListNode mH = null; // 大於區域的頭
ListNode mT = null; // 大於區域的尾
ListNode cur = head; // 當前遍歷到的結點

接下來開始遍歷連結串列，進行主流程處理，虛擬碼如下

while (cur != null) {
    // 如果head.val < pivot，則通過sH，sT構造小於區域的連結串列
    // 如果head.val > pivot，則通過mH，mT構造小於區域的連結串列
    cur = cur.next;
}
// 把兩個區域的連結串列串聯起來即可。

構造每個區域的連結串列的時候和上述荷蘭國旗問題一樣。

最後需要把兩個區域的連結串列連線起來：


        if (mT != null) {
            // 大於區域的尾置空
            mT.next = null;
        }
        
        if (sT != null) {
            // 小於區域的尾置空
            sT.next = null;
        }
        // 經過上述操作，兩個連結串列斷開連線
        if (sH == null) {
            // 小於區域的頭為空，說明只有大於區域
            return mH;
        }
        // 小於區域的頭不為空，小於區域的尾一定也不為空，直接把小於區域的尾連上大於區域的頭即可。
        sT.next = mH;
        return sH;

完整程式碼見

class Solution {
    public static ListNode partition(ListNode head, int x) {
        ListNode sH = null;
        ListNode sT = null;
        ListNode mH = null;
        ListNode mT = null;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (sH == null) {
                    sH = cur;
                } else {
                    sT.next = cur;
                }
                sT = cur;
            } else {
                // cur.val >= x
                // 都放到大於等於區域
                if (mH == null) {
                    mH = cur;
                } else {
                    mT.next = cur;
                }
                mT = cur;
            }
            cur = cur.next;
        }
        if (mT != null) {
            mT.next = null;
        }
        if (sT != null) {
            sT.next = null;
        }
        if (sH == null) {
            return mH;
        }
        sT.next = mH;
        return sH;
    }
}

演演算法和資料結構筆記

在連結串列上實現 Partition 以及荷蘭國旗問題

在連結串列上實現 Partition 以及荷蘭國旗問題

題目描述

主要思路

更多