148. Sort List - Medium

前往題目

想法

• 全部存下來，然後排序完再重新連接，但這樣就至少O(2n + nlogn)也是挺暴力了的😂

思路

這題的思路很簡單，但是指針操作一樣很容易搞混😂

1. 把list分成左半部和右半部
2. 利用mergesort把左半和右半排序好
3. 最後再把左右合併

Linked List找中心點的方法

private ListNode getMid(ListNode head) {
    // Slow fast pointer to determine the middle node
    ListNode slow = head, fast = head.next;
    // When the fast pointer is still valid
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next; // Shift twice
    }
    return slow;
}

Code

class Solution {
    public ListNode sortList(ListNode head) {
        // Base case
        if (head == null || head.next == null) {
            return head;
        }

        // Split the list
        ListNode left = head;
        ListNode right = getMid(head);
        // Hold the initial right pointer
        ListNode tmp = right.next;
        right.next = null;
        right = tmp; // Move pointer

        left = sortList(left);
        right = sortList(right);

        return merge(left, right);
    }

    private ListNode getMid(ListNode head) {
        // Slow fast pointer to determine the middle node
        ListNode slow = head, fast = head.next;
        // When the fast pointer is still valid
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next; // Shift twice
        }
        return slow;
    }

    private ListNode merge(ListNode left, ListNode right) {
        // Store the beginning
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        // traverse the nodes
        while (left != null && right != null) {
            if (left.val < right.val) {
                tail.next = left;
                left = left.next;
            } else { // left equal or larger than right
                tail.next = right;
                right = right.next;
            }

            tail = tail.next;
        }

        // Merge all the remaining nodes
        if (left != null) {
            tail.next = left;
        }
        if (right != null) {
            tail.next = right;
        }

        return dummy.next;
    }
}

2024/05/06

• 還不熟悉mergesort

2024/10/13

• 又忘了mergesort