[LeetCode] 148. Sort List

Posted on | In

Problem

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

Example 1:

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

Example 2:

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

Explanation

  1. We can use merge sort method to solve this problem. We want to split the list, first define slow, fast, and pre pointer. The pre poitner is used for pointing at the previous position of the slow pointer. All three pointers initialized to the head.

  2. Find the middle of the element in the list by using slow and fast pointer technique. If the list is 1->2->3->4, then slow is at node 3, pre is at node 2. We want to split the original list to 1->2 and 3->4, so we make pre.next = null. When there’s one node in the list, we return that node.

  3. After splitting, for the merge function taking left list and right list as parameters, if left’s value is smaller, then left.next is equal to the merge function of taking left.next and right; similar for right’s value is greater or equal to left’s value. The base case is when either of left or right is null, we return anohter list.

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode merge(ListNode left, ListNode right) {
        if (left == null) return right;
        if (right == null) return left;
        if (left.val < right.val) {
            left.next = merge(left.next, right);
            return left;
        } else {
            right.next = merge(left, right.next);
            return right;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head, pre = head;

        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        pre.next = null;
        return merge(sortList(head), sortList(slow));
    }
}