-
Notifications
You must be signed in to change notification settings - Fork 0
/
LeetCode148.go
57 lines (45 loc) · 898 Bytes
/
LeetCode148.go
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
package main
func mergaNode ( head1 , head2 *ListNode) *ListNode {
dummyHead := &ListNode{}
temp , temp1 , temp2 := dummyHead , head1 , head2
for temp1 != nil && temp2 != nil {
if temp1.Val > temp2.Val {
temp.Next = temp2
temp2 = temp2.Next
} else {
temp.Next = temp1
temp1 = temp1.Next
}
temp = temp.Next
}
if temp1 == nil {
temp.Next = temp2
} else if temp2 == nil {
temp.Next = temp1
}
return dummyHead.Next
}
func SortNode(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 mergaNode(SortNode(head,mid) , SortNode(mid , tail))
}
func sortList(head *ListNode) *ListNode {
return SortNode(head , nil)
}
func main() {
}