单链表排序

发表于 更新于

描述

给定一个节点数为n的无序单链表，对其按升序排序。

示例1

1
2
输入:  [1,3,2,4,5]
返回:  {1,2,3,4,5}

示例2

1
2
输入:  [-1,0,-2]
返回:  {-2,-1,0}

题解

分治算法

  1. 快慢指针将链表一分为二
  2. 分别对两个子链表排序
  3. 合并排序后的两个链表
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
package main

type ListNode struct{
    Val int
    Next *ListNode
}


/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
*/
func sortInList( head *ListNode ) *ListNode {
    // write code here
    if head == nil || head.Next == nil {
        return head        
    }

    fast, slow := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    second_head := slow.Next
    slow.Next = nil
    l1, l2 := sortInList(head), sortInList(second_head)

    dummy := &ListNode{}
    pre := dummy

    for l1 != nil && l2 != nil {
        if l1.Val > l2.Val {
            pre.Next = l2
            l2 = l2.Next
        } else {
            pre.Next = l1
            l1 = l1.Next
        }
        pre = pre.Next
    }

    if l1 == nil {
        pre.Next = l2
    }
    if l2 == nil {
        pre.Next = l1
    }

    return dummy.Next
}