0.单链表是否递增

//不带头结点 
int isriselk(LinkList*head)
{
    if(!head||!head->next)return 1;
    ListNode*p;
    ListNode*q;
    for(q=head,p=head->next;p!=NULL;q=p;p=p->next) 
    {
        if(q->val>p->val)
        {
            return 0;
        }
    }
    return 1;
}

1.合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围
链表长度 [0,500]。

样例
输入：1->3->5 , 2->4->5

输出：1->2->3->4->5->5

1.依次比较两个链表表头元素,将更小的插入新链表中,直到其中一表为空
2.最后会剩余一个链表,将其插入新链表即可

时间复杂度
两个链表各遍历一次，所以时间复杂度为O(n+m)
空间复杂度O(1)
代码

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode*dummy = new ListNode(0);
        ListNode*cur=dummy;

        while(l1!=NULL&l2!=NULL)
        {
            if(l1->val<l2->val)
            {
                cur->next=l1;
                l1=l1->next;
            }
            else
            {
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        if(l1!=NULL)
        {
            cur->next=l1;
        }
        else
        {
            cur->next=l2;
        }
        return dummy->next;
    }
};

两个递增的变成一个递减的。头插。带头节点的两个链表
//带有头结点的,要求合并后的链表在la中,不新增一个新链表 
void MergeList(ListNode*la,ListNode*lb)
{

    ListNode*pa=la->next;
    ListNode*pb=lb->next;
    ListNode*r;
    la->next=NULL;
    while(pa&&pb)
    {
        if(pa->val<=pb->val)
        {
            r=pa->next;
            pa->next=la->next;
            la->next=pa;
            pa=r;
        }
        else
        {
            r=pb->next;
            pb->next=la->next;
            la->next=pb;
            pb=r;   
        } 
    }
    if(pa)
    {
        pb=pa;
    }
    while(pb)
    {
        r=pb->next;
        pb->next=la->next;
        la->next=pb;
        pb=r;
    }
    delete lb;
}

2.对链表插入排序
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:
1.插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2.每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3.重复直到所有输入数据插入完为止。

算法
(插入排序) O(n2)
为了方便处理边界情况，我们建立虚拟头结点，指向原链表头部。
然后扫描原链表，对于每个节点 v，从前往后扫描结果链表，找到第一个比 v 大的节点 u，将 v 插入到 u 之前。

时间复杂度分析：一共遍历 n 个节点，对于每个节点找合适位置时，最多需要遍历 O(n) 次，所以总时间复杂度是 O(n2)。
空间复杂度:O(1)

代码

class Solution {
public:
    //不带头结点,所以创建一个虚拟头结点
    ListNode* insertionSortList(ListNode* head) {
        if(!head||!head->next)return head;
        //返回的答案链表(即排好序的链表)
        ListNode*dummy=new ListNode(-1);

        while(head)
        {
            ListNode*cur=dummy; //每次定义新的cur链表用于找新head节点插入cur链表插入何处


            // 顺序循环原链表 找到此刻插入排序链表的节点应该要放在答案链表中的位置,找到第一个大于该插入节点的位置
            //判断条件为小于等于,则是稳定的
            while(cur->next&&cur->next->val<=head->val)
            {
                //即判断cur节点
                cur=cur->next;
            }
            ListNode*nex=head->next;

            //此时head为新要插入排序链表的节点，插入cur节点后
            head->next=cur->next;
            cur->next=head;
            //head每插入一个后移动到下一个
            head=nex;
        }
        return dummy->next;

    }
};

//带头结点
ListNode* insertionSortList(ListNode* head)
{
    ListNode*p=head->next;
    head->next=NULL;
    ListNode*sub;
    while(p)
    {
        ListNode*cur=head;      
        while(cur->next&&cur->next->val<=p->val)
        {
            cur=cur->next;
        }
        //p是无序部分,要插到有序部分head的后面,p的前驱的cur,上面的循环就是找p的前驱,保留p的后部以便循环
        sub=p->next;
        p->next=cur->next;
        cur->next=p;
        p=sub;
    }
    return head;
}

3.对链表进行选择排序
代码

//带头结点
ListNode* insertionSortList(ListNode* head)
{
    //将头结点和后继节点断开
    ListNode*p=head->next;
    head->next=NULL;

    while(p)
    {
        //cur,curPrep是工作指针,max,maxPrep记录最大节点和其前驱
        ListNode*max=p;
        ListNode*maxPrep=NULL;
        ListNode*cur=p;
        ListNode*curPrep=NULL;
        while(cur)
        { 
            //>=是变稳定了
            if(cur->val>=max->val)
            {
                max=cur;
                maxPrep=curPrep;
            }
            curPrep=cur;
            cur=cur->next;
        }
        //若最大节点是无序表的第一个则移动到下一位
        if(max==p)
        {
            p=p->next;
        }
        //否则断掉最大节点
        else
        {
            maxPrep->next=maxPrep->next->next;
        }
        //将最大节点头插到head后即可
        max->next=head->next;
        head->next=max;
    }
    return head;
}

//不带头结点
ListNode* insertionSortList(ListNode* head)
{
    ListNode*dummy=new ListNode(0);

    while(head)
    {
        ListNode*cur=head;
        ListNode*curPrep=NULL;
        ListNode*max=head;
        ListNode*maxPrep=NULL;

        while(cur)
        {
            if(cur->val>=max->val)
            {
                max=cur;
                maxPrep=curPrep;
            }
            curPrep=cur;
            cur=cur->next;

        }
        if(max==head)
        {
            head=head->next;
        }
        else
        {
            maxPrep->next=maxPrep->next->next;
        }
        max->next=dummy->next;
        dummy->next=max;
    }
    return dummy->next;
}

4.归并排序(自顶向下)
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入：head = [4,2,1,3]
输出：[1,2,3,4]

对链表自顶向下归并排序的过程如下:

1.
找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2步，慢指针每次移动 1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
2.
对两个子链表分别排序。
3.
将两个排序后的子链表合并，得到完整的排序后的链表。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。

复杂度
时间复杂度：O(nlogn)，其中 n 是链表的长度。
空间复杂度：O(logn)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

代码

    ListNode *sortList(ListNode *head){
        if (!head || !head->next) return head;
        ListNode *s = head, *f = head->next;
        //找到链表的中间位置
        while (f&&f->next){        //快慢指针，注意必须前两步存在
            s = s->next;
            f = f->next->next;
        }
        ListNode *l1 = sortList(s->next);        //右链表
        s->next = NULL;        //将其断开，为两个链表
        ListNode *l2 = sortList(head);
        return merge(l1, l2);
    }
    ListNode *merge(ListNode *l1, ListNode *l2){
        auto h = new ListNode(0), r = h;//r为尾结点
        while(l1&&l2){
            if(l1->val < l2->val) r->next = l1,l1 = l1->next,r = r->next;//把l1连到尾部
            else r->next = l2,l2 = l2->next,r = r->next;
        }
        if(!l1) r->next = l2; 
        if(!l2) r->next = l1;
        return h->next;
    }

5.回文链表
给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

输入: head = [1,2,3,3,2,1]
输出: true
示例 2：

代码

class Solution {
public:
 bool isPalindrome(ListNode* head) {
        if(!head||!head->next) return true;//0个或1个数自然为真
        stack<int> stk;//存放前半个数
        ListNode*f=head;
        ListNode*s=head;
        while(f&&f->next)
        {
            stk.push(s->val);
            f=f->next->next;
            s=s->next;
        }
        //判断奇数点和偶数个点的情况，画图区分,因为f每次走两个,当f为空则是偶数点,s刚好到右半边的第一个点,否则为整个链表的中点,s为后半部分的起点
        if(f)
        {
            s=s->next;
        }
        while(s)
        {
            if(s->val!=stk.top())return false;
            s=s->next;
            stk.pop();
        }
        return true;
    }
};

手写栈
class Solution {
public:

 typedef struct{
    char *data;
    int top;
 }SqStack;  


 bool isPalindrome(ListNode* head) {
        if(!head||!head->next) return true;//0个或1个数自然为真
        stack<int> stk;//存放前半个数
        ListNode*f=head;
        ListNode*s=head;
        SqStack stk;
        stk.top=-1;
        while(f&&f->next)
        {
            stk.data[++top]=s->val; 
            f=f->next->next;
            s=s->next;
        }
        //判断奇数点和偶数个点的情况，画图区分,因为f每次走两个,当f为空则是偶数点,s刚好到右半边的第一个点,否则为整个链表的中点,s为后半部分的起点
        if(f)
        {
            s=s->next;
        }
        while(s)
        {
            if(s->val!=stk.data[stk.top--])return false;
            s=s->next;
        }
        return true;
    }
};

6.重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入：head = [1,2,3,4]
输出：[1,4,2,3]

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

复杂度分析

时间复杂度：O(N)，其中 NN 是链表中的节点数。

空间复杂度：O(1)。

代码

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==NULL||head->next==NULL||head->next->next==NULL)return;

        // 1. 找中点，让slow指向中点，或左中点位置
        ListNode*slow=head;
        ListNode*fast=head->next;

        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }

        // 2. 断开中点，反转后半部分,此时slow->next指向右半边,需要将左半边最右那个数slow的下一个指向空就分开了两个链表,然后再让slow指向右半边,slow此时为右半边第一个数然后反转即可
        ListNode*nex=slow->next;
        slow->next=NULL;
        slow=nex;
        ListNode*pre=NULL;
        while(slow)
        {
            ListNode*no=slow->next;
            slow->next=pre;
            pre=slow;
            slow=no;
        }

        // 3. 合并左链表和右边反转的链表,左边一个连一个右边连一个。
        ListNode*cur1=head;
        ListNode*cur2=pre;


        while(cur1&&cur2)
        { 
            //也可换成下列做法,每次插一个cur2的一个点到cur1的前面,然后两个cur1,cur2往后移即可
            <!--ListNode*mm=cur1->next;-->
            <!--ListNode*qq=cur2->next;-->
            <!--cur2->next=cur1->next;-->
            <!--cur1->next=cur2;-->
            <!--cur2=qq;-->
            <!--cur1=mm;-->
        }
    }
};