148. Sort List

题目

Sort a linked list in O(n log n) time using constant space complexity.

题意

对单向链表进行排序，要求时间复杂度为O(nlogn),常数空间复杂度

示例

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

题解

关于时间复杂度为O(nlogn)的排序算法，常见的有快排，堆排和归并这三种。
快排不好处理尾指针前驱指针，堆排序不好找他的子节点。使用归并可以将链表断开，然后排序好后在重写组装

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    return SortList(head)
}

func SortList(head *ListNode) *ListNode{
    if head==nil||head.Next==nil{
        return head
    }
    
    //两个指针，一个走一步，一个走两步，依次来找到中间节点
    var prev *ListNode
    slow := head
    fast := head
    for fast!=nil&&fast.Next!=nil{
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    //将链表截断
    prev.Next = nil
    
    //分治
    l1 := SortList(head)
    l2 := SortList(slow)
    
    //整合
    return Merge(l1,l2)
}

func Merge(l1 ,l2*ListNode ) *ListNode{
    h := new(ListNode)    
    p := h
    for l1!=nil&&l2!=nil{
        if l1.Val < l2.Val{
            p.Next = l1
            l1 = l1.Next
        }else{
            p.Next = l2
            l2 = l2.Next
        }
        p = p.Next
    }
    
    if l1!=nil{
        p.Next = l1  
    }
    
    if l2!=nil{
        p.Next = l2
    }
    
    return h.Next
}

总结

一开始想到的就是快排，在模拟了之后发现由于是单向的，所以不好寻找前驱指针（平时归并用的少，没有第一时间反映过来可以使用归并）。在打算使用归并后还想着能不能在原链表的基础上进行交换来局部排序，但还是会陷入寻找前驱指针的问题，所以每一次合并都是用一个新的节点来将他们串联起来。
寻找中间节点，使用两个指针来找。