148 Sort List

Search…
148 Sort List
148. Sort List​
1. Question
Sort a linked list in O(nlogn) time using constant space complexity.
2. Implementation
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode(int x) { val = x; }
7
 * }
8
 */
9
class Solution {
10
    public ListNode sortList(ListNode head) {
11
        if (head == null || head.next == null) {
12
            return head;
13
        }
14
​
15
        int len = 0;
16
        ListNode curNode = head;
17
​
18
        while (curNode != null) {
19
            curNode = curNode.next;
20
            ++len;
21
        }
22
​
23
        ListNode left = null, right = null, tail = null, dummy = null;
24
        for (int step = 1; step < len; step *= 2) {
25
            dummy = new ListNode(0);
26
            curNode = head;
27
            tail = dummy;
28
​
29
            while (curNode != null) {
30
                left = curNode;
31
                right = split(left, step);
32
                curNode = split(right, step);
33
                tail = merge(left, right, tail);
34
            }
35
            head = dummy.next;
36
        }
37
        return head;
38
    }
39
​
40
    // Split a linked list into half, where the first half contains n nodes (or all nodes)
41
    // Return the head of the second half list (or null)
42
    public ListNode split(ListNode head, int n) {
43
        for (int i = 1; head != null && i < n; i++) {
44
            head = head.next;
45
        }
46
​
47
        if (head == null) {
48
            return null;
49
        }
50
        ListNode second = head.next;
51
        head.next = null;
52
        return second;
53
    }
54
​
55
    // Merge two sorted linked list l1 and l2
56
    // Append the result to list node tail
57
    // Return the tail of merge sorted list
58
    public ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
59
        ListNode curNode = tail;
60
        while (l1 != null && l2 != null) {
61
            if (l1.val < l2.val) {
62
                curNode.next = l1;
63
                l1 = l1.next;
64
            }
65
            else {
66
                curNode.next = l2;
67
                l2 = l2.next;
68
            }
69
            curNode = curNode.next;
70
        }
71
​
72
        curNode.next = l1 == null ? l2 : l1;
73
        while (curNode.next != null) {
74
            curNode = curNode.next;
75
        }
76
        return curNode;
77
    }
78
}
Copied!
3. Time & Space Complexity
时间复杂度O(nlogn), 空间复杂度O(1)
817 Linked List Components
Topological Sort
Last modified 2yr ago
Copy link
Contents
148. Sort List
1. Question
2. Implementation
3. Time & Space Complexity
148. Sort List​

1. Question

2. Implementation

3. Time & Space Complexity

148. Sort List
