算法：排序鏈表（LeetCode）

題目：在 O(n log n) 時間複雜度和常數級空間複雜度下，對鏈表進行排序。

示例 1:

輸入: 4->2->1->3 輸出: 1->2->3->4

示例 2:

輸入: -1->5->3->4->0 輸出: -1->0->3->4->5

解題思路：首先最簡單的，遍歷鏈表，類似插入排序。O(n^2)

<code>/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    if head==nil{
        return head
    }
    for p:=head;p!=nil && p.Next!=nil;{
        if p.Next.Valp.Next.Val{//比頭小，替換為頭節點
                target:=p.Next
                p.Next=p.Next.Next
                target.Next=head
                head=target
                continue
            }
            for h:=head;h.Next!=nil;h=h.Next{
                if h.Next.Val>p.Next.Val{//選擇合適的位置
                    target:=p.Next
                    p.Next=p.Next.Next
                    ht:=h.Next
                    h.Next=target
                    h.Next.Next=ht
                    break
                }
            }
            continue
        }
        p=p.Next
    }
    return head
}/<code>

執行用時：652 ms

優化：題中要求O(n log n) ,使用歸併排序

<code>func sortList(head *ListNode) *ListNode {
    if head==nil || head.Next==nil{
        return head
    }
    slow,fast:=head,head.Next
    for fast.Next!=nil&&fast.Next.Next!=nil{//快慢指針找到中間位置
        slow,fast=slow.Next,fast.Next.Next
    }
    mid:=slow.Next
    slow.Next=nil//分成兩個鏈表各自遞歸
    left:=sortList(head)
    right:=sortList(mid)
    h :=new(ListNode)
    p:=h//合併
    for left!=nil && right!=nil{
        if left.Val>right.Val{
            h.Next=right
            right=right.Next
        }else{
            h.Next=left
            left=left.Next
        }
        h=h.Next
    }
    if left!=nil{
        h.Next=left
    }else{
        h.Next=right
    }
    return p.Next
}/<code>

執行用時：12 ms

嘗試使用快速排序：分組迭代過程中，為了不破壞鏈表的連續性，只交換結點的值。

<code>func sortList(head *ListNode) *ListNode {
    return fastSortList(head,nil)
}
func fastSortList(head *ListNode, end *ListNode) *ListNode {
	if head == end || head.Next == nil {
		return head
	}
	left := head//left表示左鏈表的最後一個結點
	p := head.Next//p來遍歷鏈表
	for p != end {
		if p.Val < head.Val {
			left = left.Next
			swapValue(left, p)
		}
		p = p.Next
	}
//head結點不變，只交換值
	swapValue(head,left)
	fastSortList(head, left)
	fastSortList(left.Next, end)
	return head
}
func swapValue(a, b *ListNode) {
	a.Val,b.Val=b.Val,a.Val
}/<code>

執行用時：300 ms