leetcode 148. 排序链表 golang实现
func sortList(head *ListNode) *ListNode {
left, right := curList(head)
// 单个的链表不再切割 否则会一直切下去
if left != nil && left.Next != nil{
left = sortList(left)
}
if right != nil && right.Next != nil{
right = sortList(right)
}
return mergeList(left, right)
}
// 利用快慢指针 找到链表中点
func curList(head *ListNode)(*ListNode, *ListNode){
if head == nil{
return nil, nil
}
fast := head.Next
slow := head
for fast != nil && fast.Next != nil{
fast = fast.Next.Next
slow = slow.Next
}
slowNext := slow.Next
slow.Next = nil
return head, slowNext
}
func mergeList(list1 *ListNode, list2 *ListNode) *ListNode {
if list1 == nil {
return list2
} else if list2 == nil {
return list1
}
var head = new(ListNode)
var cur = head
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
cur.Next = list1
list1 = list1.Next
} else {
cur.Next = list2
list2 = list2.Next
}
cur = cur.Next
}
if list1 == nil {
cur.Next = list2
} else {
cur.Next = list1
}
return head.Next
}