单链表归并排序+快排

归并排序

1. 用快慢指针获取中间点
2. 用middle指向中间点，p指向middle->next
3. middle->next=NULL，将链表拆为两段
4. 继续递归
5. 递归结束，返回新的头指针
6. 将两个头指针对应的两个链表拼接（按照归并排序的方法用一个临时头指针做基穿针引线，然后放弃临时头指针）并返回真实的头指针

#include<iostream>
using namespace std;
struct ListNode {
    public:
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    // &*point
    ListNode* ListNodes(ListNode *&p,int* v,int len){
        if(len==0){
            return nullptr;
        }
        // 初始化p然后再递归p->next
        p=new ListNode(*v);
        return ListNodes(p->next,(v+1),len-1);
    }
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* sortList(ListNode*& head) {
        // 递归到最后null或者只有一个节点就返回head
        if(head == nullptr||head->next == nullptr){
            return head;
        }
        ListNode*middle=nullptr;
        ListNode*two=head;
        ListNode*one=head;
        // 获取middle节点（一步两步双指针）
        while(two->next!=nullptr&&two->next->next!=nullptr){
            one=one->next;
            two=two->next->next;
        }
        // 用null砍断,将链表一分为二
        middle=one;
        ListNode*p=one->next;
        middle->next=nullptr;

        // 将两段各自递归
        one=sortList(head);
        two=sortList(p);
        // 回退的时候将砍断的两个链表拼接在一起,用一个临时头指针把他们串起来
        // 然后覆盖原head
        head=mergesortList(one,two);
        return head;
    }
    ListNode* mergesortList(ListNode*p1, ListNode*p2){
        ListNode* head=new ListNode();
        ListNode* mark=head;
        // 插入排序
        while(p1!=nullptr&&p2!=nullptr){
            if(p1->val>p2->val){
                    head->next=p2;
                    head=head->next;
                    p2=p2->next;
            }
            else{
                    head->next=p1;
                    head=head->next;
                    p1=p1->next;
            }
        }
        // 最后可能有段链表没有到底,需要人工拼接
        if(p1!=nullptr){
            head->next=p1;
        }
        if(p2!=nullptr){
            head->next=p2;
        }
        // 头指针丢弃
        ListNode*fr=mark;
        mark=mark->next;
        free(fr);
        return mark;
    }
};
void print(ListNode*p){
    while(p!=nullptr){
        cout<<"val:"<<p->val<<endl;
        p=p->next;
    }
}
int main(){
    // 初始化链表
    int p[]={4,2,1,3};
    ListNode* head=nullptr;
    head->ListNodes(head,p,4);

    // mergesort
    Solution solution;
    head=solution.sortList(head);
    print(head);
}

快排

正常的快排是从头尾向中间靠拢，保证p1左边都是小于a[0]，但是p2右边都是大于a[0]，不过p1和p2点上的不需要保证。

单链表的快排也使用两个指针，但都是从头遍历，保障p1左侧小于a[0]，p1与p2之间大于a[0]，但是p1和p2两点上不保障。

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func swap(a *ListNode, b *ListNode) {
    if a == b {
        // 如果俩指针是一个那就不必麻烦后面了
        return
    }
    t := a.Val
    a.Val = b.Val
    b.Val = t
}

func sortList(head *ListNode) *ListNode {
    // 只接受长度大于等于2的list
    if head == nil || head.Next == nil {
        return head
    }
    // 双指针从头到尾遍历
    var Middle1 *ListNode
    var Middle2 *ListNode

    Middle1 = head
    Middle2 = head.Next

    // 右侧负责判断与左侧的相对大小，如果右侧更小则与左侧后一位交换，然后左侧后一位再与左侧交换
    // 最后左侧指针与右侧指针各右移一位，如果相对更大则右侧右移一位
    for Middle2 != nil {
        if Middle2.Val < Middle1.Val {
            swap(Middle2, Middle1.Next)
            swap(Middle1.Next, Middle1)
            Middle2 = Middle2.Next
            Middle1 = Middle1.Next
        } else {
            Middle2 = Middle2.Next
        }
    }
    Middle2 = Middle1.Next
    Middle1.Next = nil
    Middle1 = sortList(head)
    Middle2 = sortList(Middle2)

    if Middle1 == nil {
        return Middle2
    }
    if Middle2 == nil {
        return Middle1
    }
    t := Middle1
    for t.Next != nil {
        t = t.Next
    }
    t.Next = Middle2
    return Middle1
}

func initList(List []int) *ListNode {
    if len(List) == 0 {
        return nil
    }
    L := &ListNode{List[0], nil}
    temp := L
    for i := 1; i < len(List); i++ {
        temp.Next = &ListNode{List[i], nil}
        temp = temp.Next
    }
    return L
}
func main() {
    List := []int{-1, 5, 3, 4, 0}
    list := initList(List)

    list = sortList(list)
    for t := list; t != nil; t = t.Next {
        fmt.Println(t)
    }
}