[LeetCode] 148. Sort List

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

Thought process:
In this case, merge sort does not take extra space because we are sorting a linked list. We can break the original list into pieces and merge them.
Pay attention to the base case and the initialization of fast and slow pointers in findMiddle function. Make sure to eliminate all possibilities of infinite loop.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode middle = findMiddle(head); ListNode right = middle.next; middle.next = null; return merge(sortList(head), sortList(right)); } private ListNode findMiddle(ListNode head) { ListNode fast = head.next; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } private ListNode merge(ListNode left, ListNode right) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (left != null && right != null) { if (left.val < right.val) { current.next = left; left = left.next; } else { current.next = right; right = right.next; } current = current.next; } if (left == null) { current.next = right; } else { current.next = left; } return dummy.next; } }

Time complexity:
findMiddle takes O(n). merge takes O(n). Recurrences take O(logn). The overall time complexity is O(nlogn).