leetcode之連結清單專題

目錄

• • • • 一 虛拟頭結點
      • • 1. leetcode 203.移除連結清單元素
      • 二 快慢指針
      • • 1. leetcode 876.連結清單的中間節點
        • 2. leetcode 141.環形連結清單
      • 三 反轉連結清單
      • • 1. 劍指 Offer 24.反轉連結清單
        • 2. leetcode 92.反轉連結清單II
        • 3. leetcode 25.K 個一組翻轉連結清單
      • 四 合并連結清單
      • • 1. leetcode 21.合并兩個有序連結清單
        • 2. leetcode 23.合并K個升序連結清單
      • 五 連結清單求和
      • • 1. leetcode 2.兩數相加
        • 2. leetcode 445.兩數相加 II
      • 六 排序連結清單
      • • 1. leetcode 148.排序連結清單

一 虛拟頭結點

對于連結清單題目，我們需要區分head節點是第一個有效節點還是一個虛拟頭節點（即不存放任何值，僅僅用來指向第一個有效節點），對于leetcode中關于連結清單的題目，head頭結點指的就是第一個有效節點，并不是虛拟頭節點；通常在解題中，為了友善連結清單的一些操作，我們會給連結清單設定一個虛拟頭結點，但是最終傳回連結清單的時候記得傳回虛拟頭結點的下一個節點

1. leetcode 203.移除連結清單元素

leetcode 203.移除連結清單元素

題目要求：

删除連結清單中等于給定值 val 的所有節點。

示例：

輸入: 1->2->6->3->4->5->6, val = 6

輸出: 1->2->3->4->5

public class 移除連結清單元素 {
    /**
     * 方法一：直接在原來的連結清單進行删除
     *       由于單連結清單的局限性，删除一個節點需要找到它的前一個節點
     *       那麼如果待删除節點是第一個節點head，沒有前一個節點，這種情況就得單獨處理
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements1(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        // 特殊情況：連結清單的頭結點值等于val，那麼直接将head指針往後移
        while (head != null && head.val == val) {
            head = head.next;
        }
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
    /**
     * 方法二：使用虛拟頭結點
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements2(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        // 建立一個節點，用來充當虛拟頭結點
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode cur = node;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        // 注意這裡需要傳回虛拟頭結點的下一個節點
        return node.next;
    }
}
           

二 快慢指針

1. leetcode 876.連結清單的中間節點

leetcode 876.連結清單的中間節點

題目描述：

給定一個頭結點為 head 的非空單連結清單，傳回連結清單的中間結點。如果有兩個中間結點，則傳回第二個中間結點。

示例1：

輸入：[1,2,3,4,5]

輸出：此清單中的結點 3 (序列化形式：[3,4,5])

傳回的結點值為 3 。 (測評系統對該結點序列化表述是 [3,4,5])。

注意，我們傳回了一個 ListNode 類型的對象 ans，這樣：

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL

示例2：

輸入：[1,2,3,4,5,6]

輸出：此清單中的結點 4 (序列化形式：[4,5,6])

由于該清單有兩個中間結點，值分别為 3 和 4，我們傳回第二個結點。

public class 連結清單的中間節點 {
    /**
     * 使用快慢指針，注意循環結束的條件
     * 注意：如果題目是要求當連結清單的節點數為偶數，傳回第一個中間節點，那麼循環結束的條件應該改成快指針的下一節點和下下節點都不為空
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
           

2. leetcode 141.環形連結清單

leetcode 141.環形連結清單

題目描述：

給定一個連結清單，判斷連結清單中是否有環。

/**
 * 判斷連結清單是否有環，可以使用快慢指針法，快指針一次走兩步，慢指針一次走一步，如果最終快慢指針相遇，說明有環，如果快指針為null，說明無環
 * 隻要存在環，那麼快慢指針一定會相遇，因為相對于快指針來說，慢指針是每次一步一步的去靠近快指針，那麼遲早會相遇
 * 而如果快指針每次不是走兩步，而是三步或者四步，那麼快慢指針就有可能錯過，不會相遇
 */
public class 環形連結清單 {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        // 定義快慢指針
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}
           

補充：如果題目要求是判斷連結清單是否有環，如果有環，傳回環的入口，那麼解題思路應該為：先用快慢指針判斷連結清單是否有環，如果有，則讓慢指針回到第一個節點（有效節點），快指針保持在相遇位置，然後快慢指針各走一步，當再次相遇的時候，說明到了環的入口

三 反轉連結清單

1. 劍指 Offer 24.反轉連結清單

劍指 Offer 24. 反轉連結清單

題目描述：

定義一個函數，輸入一個連結清單的頭節點，反轉該連結清單并輸出反轉後連結清單的頭節點。

示例：

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

public class 反轉連結清單 {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null; // 指向目前節點的前一個節點
        ListNode cur = head; // 指向目前節點
        ListNode next = null; // 指向目前節點的後一個節點
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
           

2. leetcode 92.反轉連結清單II

leetcode 92.反轉連結清單II

題目描述：

反轉從位置 m 到 n 的連結清單。請使用一趟掃描完成反轉。

說明:

1 ≤ m ≤ n ≤ 連結清單長度。

示例：

輸入: 1->2->3->4->5->NULL, m = 2, n = 4

輸出: 1->4->3->2->5->NULL

public class 反轉連結清單II {
    /**
     * 思路：把連結清單分成三條(前部分連結清單,反轉連結清單和後部分連結清單)
     *      找到前部分連結清單的尾節點(第m-1個節點)就可以開始反轉,最後把三個連結清單拼接
     *      前部分連結清單(1~m-1)
     *      反轉連結清單(m~n)
     *      後部分連結清單(n~最後)
     *
     * 由于1<=m<=n<=連結清單長度
     * 是以應該注意m=1和n=連結清單長度這兩種特殊情況
     *
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween1(ListNode head, int m, int n) {
        if (head == null || head.next == null) {
            return head;
        }
        // 注意：m=1和m!=1要區分處理
        if (m == 1) {
            // 定位到第n個節點
            ListNode node = head;
            for (int i = m; i < n; i++) {
                node = node.next;
            }
            // 儲存第n+1個節點
            ListNode tail = node.next;
            node.next = null;
            // 對m-n部分節點進行反轉
            ListNode reverse = reverse(head);
            // 周遊到反轉後的連結清單的最後一個節點（後面需要用到）
            ListNode end = reverse;
            while (end.next != null) {
                end = end.next;
            }
            // 讓反轉後的連結清單的最後一個節點指向第n+1個節點
            end.next = tail;
            return head;
        }
        // 首先定位到第m-1個節點
        ListNode cur = head;
        for (int i = 1; i < m - 1; i++) {
            cur = cur.next;
        }
        // 儲存第m個節點
        ListNode temp = cur.next;
        cur.next = null;
        // 定位到第n個節點
        ListNode node = temp;
        for (int i = m; i < n; i++) {
            node = node.next;
        }
        // 儲存第n+1個節點
        ListNode tail = node.next;
        node.next = null;
        // 對m-n部分節點進行反轉
        ListNode reverse = reverse(temp);
        // 周遊到反轉後的連結清單的最後一個節點（後面需要用到）
        ListNode end = reverse;
        while (end.next != null) {
            end = end.next;
        }
        // 讓第m-1個節點指向反轉後的連結清單
        cur.next = reverse;
        // 讓反轉後的連結清單的最後一個節點指向第n+1個節點
        end.next = tail;
        return head;
    }

    /**
     * 使用虛拟頭結點：好處是不需要對m=1和m!=1區分讨論
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween2(ListNode head, int m, int n) {
        if (head == null || head.next == null) {
            return head;
        }
        // 定義一個虛拟頭結點
        ListNode newNode = new ListNode(0);
        newNode.next = head;
        // 首先定位到第m-1個節點
        ListNode cur = newNode;
        for (int i = 1; i < m - 1; i++) {
            cur = cur.next;
        }
        // 儲存第m個節點
        ListNode temp = cur.next;
        cur.next = null;
        // 定位到第n個節點
        ListNode node = temp;
        for (int i = m; i < n; i++) {
            node = node.next;
        }
        // 儲存第n+1個節點
        ListNode tail = node.next;
        node.next = null;
        // 對m-n部分節點進行反轉
        ListNode reverse = reverse(temp);
        // 周遊到反轉後的連結清單的最後一個節點（後面需要用到）
        ListNode end = reverse;
        while (end.next != null) {
            end = end.next;
        }
        // 讓第m-1個節點指向反轉後的連結清單
        cur.next = reverse;
        // 讓反轉後的連結清單的最後一個節點指向第n+1個節點
        end.next = tail;
        return newNode.next;
    }
    /**
     * 反轉連結清單
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
           

3. leetcode 25.K 個一組翻轉連結清單

leetcode 25.K 個一組翻轉連結清單

題目描述：

給你一個連結清單，每 k 個節點一組進行翻轉，請你傳回翻轉後的連結清單。k 是一個正整數，它的值小于或等于連結清單的長度。如果節點總數不是 k 的整數倍，那麼請将最後剩餘的節點保持原有順序。

示例：

給你這個連結清單：1->2->3->4->5

當 k = 2 時，應當傳回: 2->1->4->3->5

當 k = 3 時，應當傳回: 3->2->1->4->5

public class k個一組翻轉連結清單 {
    /**
     * 使用遞歸解法
     * 思路：先對連結清單的前k個節點進行反轉，然後将反轉後連結清單的最後一個節點指向k個節點之後的剩餘節點（這部分節點直接使用遞歸反轉）
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 遞歸的出口，如果連結清單為空或者隻有一個節點，無需反轉
        if (head == null || head.next == null) {
            return head;
        }
        // 先對連結清單的前k個節點進行反轉(由于是遞歸處理，是以這裡需要考慮連結清單的節點數小于k的情況）
        // 1.定位到連結清單的第k個節點
        ListNode start = head;
        ListNode end = head;
        for (int i = 0; i < k - 1 && end != null; i++) {
            end = end.next;
        }
        // 退出循環，如果end為null，說明連結清單的節點數小于k，無需反轉
        if (end == null) {
            return head;
        }
        // 2.儲存第k個節點的後一個節點，防止連結清單斷聯
        ListNode temp = end.next;
        end.next = null;
        // 3.對k個節點進行反轉操作
        ListNode reverse = reverse(start);
        // 4.對于已經反轉好的k個節點，周遊到最後一個節點
        ListNode node = reverse;
        while (node.next != null) {
            node = node.next;
        }
        // 将反轉後連結清單的最後一個節點指向k個節點之後的剩餘節點（這部分節點直接使用遞歸反轉）
        node.next = reverseKGroup(temp, k);
        return reverse;
    }
    /**
     * 反轉連結清單
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
           

四 合并連結清單

1. leetcode 21.合并兩個有序連結清單

leetcode 21.合并兩個有序連結清單

題目描述：

将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。

示例1：

輸入：l1 = [1,2,4], l2 = [1,3,4]

輸出：[1,1,2,3,4,4]

示例2：

輸入：l1 = [], l2 = []

輸出：[]

public class 合并兩個有序連結清單 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
                cur = cur.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            }
        }
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return head.next;
    }
    /**
     * 遞歸法
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }
}
           

2. leetcode 23.合并K個升序連結清單

leetcode 23.合并K個升序連結清單

題目描述：

給你一個連結清單數組，每個連結清單都已經按升序排列。請你将所有連結清單合并到一個升序連結清單中，傳回合并後的連結清單。

示例1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]

輸出：[1,1,2,3,4,4,5,6]

解釋：連結清單數組如下：

[1->4->5,1->3->4,2->6]

将它們合并到一個有序連結清單中得到。

1->1->2->3->4->4->5->6

示例2：

輸入：lists = []

輸出：[]

示例3：

輸入：lists = [[]]

輸出：[]

public class 合并K個升序連結清單 {
    /**
     * 方法一：借助優先隊列實作堆排序
     *  思路：維護一個根據連結清單的第一個節點的值進行排序的小根堆，首先将所有連結清單入堆，然後依次彈出堆中的堆頂元素
     *       由于是小根堆，是以每次出堆的都是所有連結清單中第一個節點值最小的那個連結清單
     *       将出堆的這個連結清單的第一個節點添加到結果連結清單中，并将該連結清單以第二個節點作為頭結點的形式入堆，繼續維護一個小根堆
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        // 建立一個大小為k的小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        // 所有連結清單入堆
        for (ListNode listNode : lists) {
            if (listNode == null) {
                continue;
            }
            queue.offer(listNode);
        }
        // 建立一個帶頭結點的結果連結清單
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (!queue.isEmpty()) {
            // 堆頂元素彈出
            ListNode node = queue.poll();
            // 如果堆頂元素指針域不為空，那麼後半部分連結清單繼續入堆
            ListNode next = node.next;
            node.next = null;
            if (next != null) {
                queue.offer(next);
            }
            cur.next = node;
            cur = cur.next;
        }
        return head.next;
    }
}
           

五 連結清單求和

1. leetcode 2.兩數相加

leetcode 2.兩數相加

題目描述：

給你兩個 非空 的連結清單，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的，并且每個節點隻能存儲 一位 數字。請你将兩個數相加，并以相同形式傳回一個表示和的連結清單。你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例1：

輸入：l1 = [2,4,3], l2 = [5,6,4]

輸出：[7,0,8]

解釋：342 + 465 = 807

示例2：

輸入：l1 = [0], l2 = [0]

輸出：[0]

示例3：

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

輸出：[8,9,9,9,0,0,0,1]

public class 兩數相加 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 建立新連結清單的虛拟頭結點
        ListNode head = new ListNode(0);
        // 輔助節點來定位新連結清單
        ListNode cur = head;
        // 輔助變量代表是否向上一位進1
        int count = 0;
        // 循環判斷的條件不要忘了加上 count!=0 這個條件
        while (l1 != null || l2 != null || count != 0) {
            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;
            int sum = val1 + val2 + count;
            count = sum / 10;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = cur.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 注意傳回的是第一個節點，而不是虛拟頭結點
        return head.next;
    }
}
           

2. leetcode 445.兩數相加 II

leetcode 445.兩數相加 II

題目描述：

給你兩個 非空 連結清單來代表兩個非負整數。數字最高位位于連結清單開始位置。它們的每個節點隻存儲一位數字。将這兩數相加會傳回一個新的連結清單。你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。

進階：如果輸傳入連結表不能修改該如何處理？換句話說，你不能對清單中的節點進行翻轉。

示例：

輸入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 8 -> 0 -> 7

public class 兩數相加II {
    /**
     * 方法一：先對連結清單進行翻轉，最終将結果連結清單再翻轉一次
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        // 先對連結清單l1和l2進行反轉
        ListNode r1 = reverse(l1);
        ListNode r2 = reverse(l2);
        // 對反轉後的連結清單進行計算
        // 1.建立新連結清單的虛拟頭結點
        ListNode head = new ListNode(0);
        // 2.輔助節點來定位新連結清單
        ListNode cur = head;
        // 3.輔助變量代表是否向上一位進1
        int count = 0;
        // 4.循環判斷的條件不要忘了加上 count!=0 這個條件
        while (r1 != null || r2 != null || count != 0) {
            int val1 = r1 != null ? r1.val : 0;
            int val2 = r2 != null ? r2.val : 0;
            int sum = val1 + val2 + count;
            count = sum / 10;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = cur.next;
            if (r1 != null) {
                r1 = r1.next;
            }
            if (r2 != null) {
                r2 = r2.next;
            }
        }
        // 對結果連結清單進行反轉一次得到最終結果
        return reverse(head.next);
    }

    /**
     * 反轉連結清單
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 方法二：使用棧
     *  思路：由于我們希望對連結清單的節點進行逆序操作，這時候可以想到棧
     *       将兩個連結清單的所有節點先依次放到兩個棧中，最後再分别彈出進行計算
     *       存放結果的連結清單再使用頭插法插入節點
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        // 建立兩個棧
        LinkedList<Integer> stack1 = new LinkedList();
        LinkedList<Integer> stack2 = new LinkedList();
        // 依次将兩個連結清單的節點值push到棧中
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        // 建立一個帶有頭結點的連結清單，用來存放結果值
        ListNode head = new ListNode(0);
        // 輔助變量代表是否向上一位進1
        int count = 0;
        // 依次彈出兩個棧中的元素進行計算
        while (!stack1.isEmpty() || !stack2.isEmpty() || count != 0) {
            int val1 = stack1.size() > 0 ? stack1.pop() : 0;
            int val2 = stack2.size() > 0 ? stack2.pop() : 0;
            int sum = val1 + val2 + count;
            count = sum / 10;
            ListNode node = new ListNode(sum % 10);
            // 使用頭插法插傳入連結表
            node.next = head.next;
            head.next = node;
        }
        return head.next;
    }
}
           

六 排序連結清單

1. leetcode 148.排序連結清單

leetcode 148.排序連結清單

題目描述：

給你連結清單的頭結點 head ，請将其按 升序 排列并傳回 排序後的連結清單 。

進階：你可以在 O(n log n) 時間複雜度和常數級空間複雜度下，對連結清單進行排序嗎？

示例1：

輸入：head = [4,2,1,3]

輸出：[1,2,3,4]

示例2：

輸入：head = [-1,5,3,4,0]

輸出：[-1,0,3,4,5]

示例3：

輸入：head = []

輸出：[]

public class 排序連結清單 {
    /**
     * 方法一：堆排序
     *  思路：維護一個根據連結清單的節點值進行排序的小根堆，周遊連結清單中的每個節點，讓每個節點一次入堆
     *  （注意：入堆的節點應該将其指針域設定為空，讓該節點成為一個獨立的節點方可入堆，否則會導緻整條連結清單入堆，産生死循環）
     *  待所有節點入堆完畢之後，再依次彈出堆中的每個節點插入到新連結清單的尾部即可，由于是小根堆，是以會根據節點值從小到大出堆
     * @param head
     * @return
     */
    public ListNode sortList1(ListNode head) {
        if (head == null) {
            return null;
        }
        // 建立小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        // cur節點用來周遊連結清單
        ListNode cur = head;
        // temp節點用來儲存目前節點的下一節點，防止連結清單斷聯，因為要将目前節點的指針域置空
        ListNode temp = null;
        // 連結清單中所有節點依次入堆
        while (cur != null) {
            temp = cur.next;
            cur.next = null;
            queue.offer(cur);
            cur = temp;
        }
        // 建立一個帶有虛拟頭結點的連結清單
        ListNode newNode = new ListNode(0);
        cur = newNode;
        // 依次出堆，使用尾插法插傳入連結表的尾部
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }

        return newNode.next;
    }
    /**
     * 方法二：歸并排序/自頂向下的歸并排序（使用遞歸實作，時間複雜度是O(nlogn)，空間複雜度不為O(1))
     *  思路：歸并排序使用分治思想，先将連結清單分成兩半，分别進行排序，再将排好序的兩個有序連結清單進行合并
     * @param head
     * @return
     */
    public ListNode sortList2(ListNode head) {
        // 遞歸終止的條件
        if (head == null || head.next == null) {
            return head;
        }
        // 使用快慢指針法定位到連結清單的中間節點（如果連結清單節點數是偶數，傳回第一個中間節點）
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 退出循環時，slow節點為中間節點
        // 用一個輔助節點來儲存中間節點的下一個節點
        ListNode temp = slow.next;
        // 将連結清單從中間節點斷開成兩部分
        slow.next = null;
        // 遞歸對中間節點左右兩部分連結清單繼續進行拆分
        ListNode l1 = sortList2(head);
        ListNode l2 = sortList2(temp);
        // 合并有序連結清單
        ListNode res = mergeTwoLists(l1, l2);
        return res;
    }
    /**
     * 方法三：歸并排序/自底向上的歸并排序（使用循環實作，時間複雜度是O(nlogn)，空間複雜度為O(1))
     *  思路：
     * @param head
     * @return
     */
    public ListNode sortList3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 計算連結清單的長度
        ListNode node = head;
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }
        // 建立一個虛拟頭結點友善操作
        ListNode newNode = new ListNode(0);
        newNode.next = head;
        // 第一次循環步長為1、第二次為2、第三次為4……直至步長大于等于連結清單長度退出循環
        for (int step = 1; step < len; step *= 2) {
            // 輔助節點cur用來周遊連結清單，輔助節點pre用來指向每次排好序的子連結清單
            // 每次循環開始，cur和pre都得回到連結清單頭
            // 注意：這裡cur必須是指向虛拟頭結點的下一個節點，不能指向head，因為head指向的是初始連結清單的第一個節點
            //      排序之後連結清單的第一個節點可能發生改變了，也就是head不一定是再指向連結清單第一個節點了
            ListNode cur = newNode.next;
            ListNode pre = newNode;
            while (cur != null) {
                ListNode node1 = cur; // 第一部分頭結點
                ListNode node2 = split(node1, step); // 第二部分頭結點
                cur = split(node2, step); // 更新cur
                ListNode listNode = mergeTwoLists(node1, node2); // 對兩部分有序連結清單進行合并，并傳回頭結點
                pre.next = listNode; // pre的指針域指向排好序的子連結清單
                // pre節點移動到排好序的子連結清單最後一個節點
                while (pre.next != null) {
                    pre = pre.next;
                }
            }
        }
        return newNode.next;
    }
    /**
     * 連結清單斷鍊操作：并傳回斷鍊後第二部分連結清單頭
     * @param head
     * @param step：步長（可以了解成斷開的第一部分連結清單節點數）
     * @return
     */
    public ListNode split(ListNode head,int step){
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        // 不要忘記步長大于連結清單節點數的情況
        for (int i = 1; i < step && cur.next != null; i++) {
            cur = cur.next;
        }
        ListNode temp = cur.next;
        cur.next = null; // 切斷連接配接
        return temp;
    }
    /**
     * 合并兩個有序連結清單
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
                cur = cur.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            }
        }
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return head.next;
    }
}