148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。原链表是无序的！
注意：题目要求时间复杂度为O(nlogn),空间复杂度为O(1)
对数组做归并排序需要的空间复杂度为O(n)—>新开辟数组O(n)+递归调用函数O(logn);
对链表做归并排序可以通过修改引用来更改节点位置，因此不需要向数组一样开辟额外的O(n)空间，但是只要是递归就需要消耗log(n)的空间复杂度，要达到O(1)空间复杂度的目标，得使用迭代法。
因此对于链表进行排序有两种方案：
（1）递归实现归并排序（空间复杂度不符合要求）
（2）迭代实现归并排序
思路
看到时间复杂度的要求，而且是链表，归并排序比较好做。
都知道归并排序要先归（二分），再并。两个有序的链表是比较容易合并的。
二分到不能再二分，即递归压栈压到链只有一个结点（有序），于是在递归出栈时进行合并。
合并两个有序的链表，合并后的结果返回给父调用，一层层向上，最后得出大问题的答案。
时间复杂度是 O(nlogn)
空间复杂度是 O(logn)
伪代码
func sortList (head) {对链表进行二分l = sortList(左链) // 已排序的左链r = sortList(右链) // 已排序的右链merged = mergeList(l, r) // 进行合并return merged // 返回合并的结果给父调用}
二分、merge 函数
二分，用快慢指针法，快指针走两步，慢指针走一步，快指针越界时，慢指针正好到达中点，只需记录慢指针的前一个指针，就能断成两链。
- merge 函数做的事是合并两个有序的左右链
//简化代码，时间nlogn，空间O1
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
second_head := slow.Next
slow.Next = nil // 切断前后两半链表
dummy := &ListNode{}
pre := dummy //l1, l2 := head, second_head //错误示范
l1, l2 := sortList(head), sortList(second_head) // 归并 + 排序
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
pre.Next = l1
l1 = l1.Next
} else {
pre.Next = l2
l2 = l2.Next
}
pre = pre.Next
}
if l1 == nil {
pre.Next = l2
}
if l2 == nil {
pre.Next = l1
}
return dummy.Next
}
//自顶向下，迭代，找中点，先分，再比较大小，合并； 不行，要自底向上
//我理解是On*On,其实时间是On*logN, 因为链表的特殊性，空间logN
//实际上，找中点，是分成无数为1的，而不是就分成两个就完事了，所以时间是logN
//1,快慢指针找中点，因为原来链表无序，所以不能简单二分后，就直接比较头节点，合并
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil { //递归出口，二分到变成最小的，一个个的链表，退出
return head
}
slow ,fast := head, head
var pre *ListNode //定义偶数，中点的前面一个节点
for fast != nil && fast.Next != nil {
pre = slow //双，前数
slow = slow.Next
fast = fast.Next.Next
}
pre.Next = nil //断链，不然会成环，画个图辅助一下
//slow.Next =nil
l := sortList(head)
r := sortList(slow)
return mergeList(l, r)
}
//2，两两合并，logN个小链表，要遍历N次
func mergeList(l1,l2 *ListNode) *ListNode {
dummy := &ListNode{Val:0} //定义的是哑结点链表，方法一 定义表dummy
prev := dummy //prev是哑结点,最后返回dummy.Next
//prehead := &ListNode{} //定义一个头指针，不停的往前走==prev，方法二，prehead动态头
//result := prehead //暂存头指针，日后从头的初始状态推完整链表！最后返回result.Next
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
prev.Next = l1
l1 = l1.Next
} else {
prev.Next = l2
l2 = l2.Next
}
prev = prev.Next
}
if l1 != nil {
prev.Next = l1
}
if l2 != nil {
prev.Next = l2
}
return dummy.Next //返回是是链表，prev是动态的指针，方法二就是result暂存的头指针
}
如果死套排序数组的快排，那么肯定难了（因为：链表交换两个节点比数组复杂太多了），而且链表的遍历方式是单向的，使用左右指针并不好处理。让我们回想一下，快排的定义：
1、选取一个基准值
2、遍历，将小于基准的放到左边，大于的放到右边
3、递归执行
那么对于链表，条件一不需要变，条件三也不需要，需要变的只有第二个条件。如何将小的大的分开呢？一个好方法是我们只需要重新定义三个哨兵节点，分别指向小于，等于，大于的链表的节点即可：以 -1->5->3->4->0为例，以3为基准，lhead:{-1,0} , mhead{3}, rhead{4,5}.将这三个连起来即可
本题解只是为了解决面试可能会问到这个，并不满足题意，空间复杂度为O(log(n))
//链表快排(分为三部分实现)
func sortList(head *ListNode) *ListNode {
return quicksort(head)
}
func quicksort(head *ListNode)*ListNode{
//出递归条件（没有节点或者只有一个节点时，不需要再分）
if head==nil || head.Next==nil{
return head
}
//遍历链表，将其分为三部分（三个哨兵节点）
lhead:=&ListNode{-1,nil}//小于基准值
mhead:=&ListNode{-1,nil}//等于基准值
rhead:=&ListNode{-1,nil}//大于基准值
left,mid,right:=lhead,mhead,rhead
//基准值不一定非以最左边为基准
pivot:=head.Val//基准值（以最左边的节点为基准）
//遍历链表
for p:=head;p!=nil;p=p.Next{
if p.Val<pivot{ //小于给左边
left.Next=p
left=left.Next
}else if p.Val > pivot{ //大于给右边
right.Next=p
right=right.Next
}else{ //等于去中间
mid.Next=p
mid=mid.Next
}
}
//将左中右节点值最后设为nil（防止后面还连着东西）
left.Next=nil
mid.Next=nil
right.Next=nil
//递归处理左右段
lhead.Next=quicksort(lhead.Next)
rhead.Next=quicksort(rhead.Next)
//将左右段拼接起来
//找到左端的尾节点
getTail(lhead).Next=mhead.Next
//找到中间的尾节点
getTail(mhead).Next=rhead.Next
return lhead.Next
}
//取得尾节点
func getTail(head *ListNode)*ListNode{
for head.Next!=nil{
head=head.Next
}
return head
}
若有收获，就点个赞吧
0 人点赞
