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;
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/sort-list/
    // Time: O(NlogN)
    // Space: O(logN)
    class Solution {
        ListNode* splitList(ListNode *head) {
            ListNode dummy, *p = &dummy, *q = &dummy;
            dummy.next = head;
            while (q && q->next) {
                q = q->next->next;
                p = p->next;
            }
            auto next = p->next;
            p->next = NULL;
            return next;
        }
        ListNode *mergeList(ListNode *a, ListNode *b) {
            ListNode head, *tail = &head;
            while (a && b) {
                ListNode *node;
                if (a->val <= b->val) {
                    node = a;
                    a = a->next;
                } else {
                    node = b;
                    b = b->next;
                }
                tail->next = node;
                tail = node;
            }
            if (a) tail->next = a;
            if (b) tail->next = b;
            return head.next;
        }
    public:
        ListNode* sortList(ListNode* head) {
            if (!head || !head->next) return head;
            auto b = splitList(head);
            return mergeList(sortList(head), sortList(b));
        }
    };
    
  • # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
      def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head:
          fast = slow = head
          pre = None
    
          while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
    
          if not pre:
            return head
          pre.next = None
    
          left = self.sortList(head)
          right = self.sortList(slow)
    
          p = dummy = ListNode(-1)
          while left and right:
            if left.val < right.val:
              p.next = left
              left = left.next
            else:
              p.next = right
              right = right.next
            p = p.next
    
          if left:
            p.next = left
          if right:
            p.next = right
          return dummy.next
    
    

All Problems

All Solutions