[Leetcode] Problem 148 - Sort List

Posted on | In ,

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up

Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example

No.1

0XGGHf.jpg

Input: head = [4,2,1,3]

Output: [1,2,3,4]

No.2

0Xrsqe.jpg

Input: head = [-1,5,3,4,0]

Output: [-1,0,3,4,5]

No.3

Input: head = []

Output: []

Constraints

  • The number of nodes in the list is in the range [0, 5 * 10^4].
  • -10^5 <= Node.val <= 10^5

Code

1
2
3
4
5
6
7
8
9
10
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
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
58
59
60
61
62
63
64
65
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
        return head;

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

    while (head != null) {
        head = head.next;
        length++;
    }

    for (int i = 1; i < length; i <<= 1) {
        ListNode current = dummy.next;
        ListNode tail = dummy;

        while (current != null) {
            ListNode l1 = current;
            ListNode l2 = split(l1, i);
            current = split(l2, i);
            ListNode[] merged = merge(l1, l2);
            tail.next = merged[0];
            tail = merged[1];
        }
    }

    return dummy.next;
}

private ListNode split(ListNode head, int n) {
    while (head != null && --n > 0)
        head = head.next;

    ListNode rest = head == null ? null : head.next;

    if (head != null)
        head.next = null;

    return rest;
}

private ListNode[] merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val > l2.val) {
            ListNode temp = l2;
            l2 = l1;
            l1 = temp;
        }

        tail.next = l1;
        tail = tail.next;
        l1 = l1.next;
    }

    tail.next = l1 == null ? l2 : l1;

    while (tail.next != null)
        tail = tail.next;

    return new ListNode[] {dummy.next, tail};
}