leetcode-148-Sort-List

发表于   |  

描述

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

分析

对链表进行排序，要求复杂度是 $O(nlog(n))$，能达到这个复杂度要求的有快速排序、希尔排序、归并排序、堆排序，而归并排序对应链表来说是比较好实现的。

解决方案1（Python）

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def mySort(head, tail):
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
            fast = slow = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            middle = slow
            return merge(mySort(head, middle), mySort(middle, tail))
        
        def merge(head1, head2):
            dummyHead = ListNode(0)
            tmp, tmp1, tmp2 = dummyHead, head1, head2
            
            while tmp1 and tmp2:
                if tmp1.val <= tmp2.val:
                    tmp.next = tmp1
                    tmp1 = tmp1.next
                else:
                    tmp.next = tmp2
                    tmp2 = tmp2.next
                tmp = tmp.next
            if tmp1:
                tmp.next = tmp1
            elif tmp2:
                tmp.next = tmp2
            return dummyHead.next
        return mySort(head, None)

解决方案2(Java)

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        
        ListNode p1 = sortList(head);
        ListNode p2 = sortList(fast);
        
        return mergeList(p1, p2);
    }
    
    private ListNode mergeList(ListNode p1, ListNode p2) {
        if (p1 == null) {
            return p2;
        } else if (p2 == null) {
            return p1;
        } else if (p1 == null && p2 == null) {
            return null;
        }
        
        ListNode head = new ListNode(0);
        ListNode p = head;
        while(p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        
        if (p1 != null) {
            p.next = p1;
        } else if (p2 != null) {
            p.next = p2;
        }
        
        return head.next;
    }
}

解决方案2（Golang）

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func merge(head1, head2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    
    head1Now, head2Now, now := head1, head2, dummyHead
    
    for head1Now != nil && head2Now != nil {
        if head1Now.Val <= head2Now.Val {
            now.Next = head1Now
            head1Now = head1Now.Next
        } else {
            now.Next = head2Now
            head2Now = head2Now.Next
        }
        now = now.Next
    }
    
    if head1Now != nil {
        now.Next = head1Now
    } else if head2Now != nil {
        now.Next = head2Now
    }
    return dummyHead.Next
}

func sort(head, tail *ListNode) *ListNode {
    if head == nil {
        return head
    }
    
    if head.Next == tail {
        head.Next = nil
        return head
    }
    slow, fast := head, head
    for fast != tail {
        slow = slow.Next
        fast = fast.Next
        if fast != tail {
            fast = fast.Next
        }
    }
    mid := slow
    return merge(sort(head, mid), sort(mid, tail))
}

func sortList(head *ListNode) *ListNode {
    return sort(head, nil)
}

相关问题

题目来源