Question

Formatted question description: https://leetcode.ca/all/148.html

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

@tag-linkedlist

Algorithm

The title limits the time to be O(nlgn). Only

  • quick sort,
  • merge sort, and
  • heap sort meet the requirements. According to the characteristics of singly linked lists, merge sort is most suitable.

To do merge sort, the middle node of the list should be found. Use two pointers to find the middle node. Each time the fast pointer moves two steps and the slow pointer moves one step. When the fast pointer moves to the end, the slow pointer points the middle node. After finding the middle node, do merge sort for two parts of the node respectively, and merge the two parts after both parts are sorted.

Two merge two parts of a list, always find the node with the smallest number each time and append the node to the sorted list.

Code

Java

public class Sort_List {

    public class Solution {
        /**
         * Definition for singly-linked list.
         * class ListNode {
         * int val;
         * ListNode next;
         * ListNode(int x) {
         * val = x;
         * next = null;
         * }
         * }
         */

        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;

            ListNode dummy = new ListNode(0);
            dummy.next = head;

            ListNode prev = dummy;
            ListNode slow = head;
            ListNode fast = head;

            // 每次都要找中点,复杂度略高啊
            while (fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }

            ListNode left = head; // eg. [1,2]
            ListNode right = slow;
            prev.next = null; // cut

            ListNode sortedLeft = sortList(left);
            ListNode sortedRight = sortList(right);

            return mergeSorted(sortedLeft, sortedRight);
        }

        public ListNode mergeSorted(ListNode left, ListNode right) {
            ListNode dummy = new ListNode(0);

            ListNode current = dummy;

            while (left != null || right != null) {
                int lval = left == null ? Integer.MAX_VALUE : left.val;
                int rval = right == null ? Integer.MAX_VALUE : right.val;

                if (lval < rval) {
                    current.next = new ListNode(lval);
                    left = left.next; // I missed this...
                } else {
                    current.next = new ListNode(rval);
                    right = right.next;
                }

                current = current.next;
            }

            return dummy.next;
        }
    }


    // constant extra space using Bottom Up Approach
    class Solution_bottom_up_merge_sort {
        ListNode tail = new ListNode(0);
        ListNode nextSubList = new ListNode(0);

        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            int n = getCount(head);
            ListNode start = head;
            ListNode dummyHead = new ListNode(0);
            for (int size = 1; size < n; size = size * 2) {
                tail = dummyHead;
                while (start != null) {
                    if (start.next == null) {
                        tail.next = start;
                        break;
                    }
                    ListNode mid = split(start, size);
                    merge(start, mid);
                    start = nextSubList;
                }
                start = dummyHead.next;
            }
            return dummyHead.next;
        }

        ListNode split(ListNode start, int size) {
            ListNode midPrev = start;
            ListNode end = start.next;
            //use fast and slow approach to find middle and end of second linked list
            for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
                if (end.next != null) {
                    end = (end.next.next != null) ? end.next.next : end.next;
                }
                if (midPrev.next != null) {
                    midPrev = midPrev.next;
                }
            }
            ListNode mid = midPrev.next;
            midPrev.next = null;
            nextSubList = end.next;
            end.next = null;
            // return the start of second linked list
            return mid;
        }

        void merge(ListNode list1, ListNode list2) {
            ListNode dummyHead = new ListNode(0);
            ListNode newTail = dummyHead;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    newTail.next = list1;
                    list1 = list1.next;
                    newTail = newTail.next;
                } else {
                    newTail.next = list2;
                    list2 = list2.next;
                    newTail = newTail.next;
                }
            }
            newTail.next = (list1 != null) ? list1 : list2;
            // traverse till the end of merged list to get the newTail
            while (newTail.next != null) {
                newTail = newTail.next;
            }
            // link the old tail with the head of merged list
            tail.next = dummyHead.next;
            // update the old tail to the new tail of merged list
            tail = newTail;
        }

        int getCount(ListNode head) {
            int cnt = 0;
            ListNode ptr = head;
            while (ptr != null) {
                ptr = ptr.next;
                cnt++;
            }
            return cnt;
        }
    }

}

All Problems

All Solutions