LeetCode-148.排序链表 - sheep44044的小站

链表#

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

1
输入：head = [4,2,1,3]
2
输出：[1,2,3,4]

示例 2：

1
输入：head = [-1,5,3,4,0]
2
输出：[-1,0,3,4,5]

示例 3：

1
输入：head = []
2
输出：[]

归并排序的解法

很神奇

思路：这个问题就是用归并排序解决的，这里可以分为两部分1.分解和 2. 合成。

分解为一个个链表，依靠快慢指针和递归，直到触发if head == nil || head.Next == nil {}返回一个链表
就是 21. 合并两个有序链表 的写法

Ps: 这个代码的递归的逻辑很像中间件的洋葱模型，返回一个链表后，再不断地return mergeTwoLists(left, right)

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func sortList(head *ListNode) *ListNode {
9
    if head == nil || head.Next == nil {
10
        return head
11
    }
12

13
    slow, fast := head, head.Next
14
    for fast != nil && fast.Next != nil {
15
        slow = slow.Next
16
        fast = fast.Next.Next
17
    }
18

19
    mid := slow.Next
20
    slow.Next = nil
21

22
    left := sortList(head)
23
    right := sortList(mid)
24

25
    return mergeTwoLists(left, right)
26
}
27

28
func mergeTwoLists(list1, list2 *ListNode) *ListNode {
29
    dummy := &ListNode{}
30
    cur := dummy
31

32
    for list1 != nil && list2 != nil {
33
        if list1.Val < list2.Val {
34
            cur.Next = list1
35
            list1 = list1.Next
36
        } else {
37
            cur.Next = list2
38
            list2 = list2.Next
39
        }
40
        cur = cur.Next
41
    }
42

43
    if list1 != nil {
44
        cur.Next = list1
45
    } else {
46
        cur.Next = list2
47
    }
48

49
    return dummy.Next
50
}