【算法】链表专题

• 链表常用技巧和操作总结：

1.先画图，直观形象便于理解，按照画图规律写代码
2.引入虚拟头节点，可确保每一个节点的处理逻辑相同，同时避免边界条件的判断
3.不要吝啬空间，大胆定义变量。在进行改变多个链接顺序时，直接创建变量进行链接可避免链表断裂等情况，用一定的空间换简单的操作
4.快慢双指针操作可以处理 判环问题、找链表的入口问题，找链表中倒数第n个节点问题
5.创建新节点用new，在堆上创建空间记得释放。熟悉尾插、头插(逆序链表)等操作

一 . (2.) 两数相加

算法原理：
1.两个链表都是逆序存储数字的，即两个链表的个位数、⼗位数等都已经对应，可以直接相加。如果给一个正序的链表，计算加法也需要先逆置，因为加法先确定的是个位，因为往后的位可能产生进位，不方便直接创建节点并链接，所以尾插形成链表的过程中先尾插的一定是个位所在节点。
2.在相加过程中，我们要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加。如果产⽣进位的位置在链表尾部，即答案位数⽐原链表位数⻓⼀位，还需要再 new ⼀个结点储存最⾼位。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode*cur1=l1,*cur2=l2;
        ListNode* newhead=new ListNode(0);//创建虚拟头节点
        ListNode* tail=newhead;//记录尾节点
        int t=0;//记录进位情况
        while(cur1||cur2||t)//或判断，三者都不为空的情况结束循环
        {//注意不为空时才能对节点进行的操作
            if(cur1) t+=cur1->val,cur1=cur1->next;;
            if(cur2) t+=cur2->val,cur2=cur2->next;;
            tail->next=new ListNode(t%10);;
            tail=tail->next;
            t/=10;//保留十位，判断进位
        }
        tail=newhead->next;
        delete newhead;//释放new的节点，避免内存泄漏
        return tail;
    }
};

二. (24.) 两两交换链表中的节点

算法原理：1.递归 2.循环迭代的方式
1.讲解法2，定义头节点，方便头两个元素交换判断，并且与后面元素处理交换保持一样的逻辑条件。
2.交换链表时可以新定义涉及到的四个节点，直接改变链接关系即可，这样以不大的空间代价避免了交换中链表断开等情况，方便处理
3.判断循环结束条件，分节点个数奇偶情况判断

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //特殊情况判断,避免创建next和nnext时空指针访问
        if(head==nullptr||head->next==nullptr) return head;

        ListNode* newhead=new ListNode(0);
        newhead->next=head;
        ListNode* prev=newhead,*cur=prev->next,*next=cur->next,*nnext=next->next;
        while(cur&&next)
        {
            //进行交换的逻辑
            prev->next=next;
            next->next=cur;
            cur->next=nnext;
            //更新指针，进行下次交换
            prev=cur;
            cur=nnext;
            if(cur) next=cur->next;
            if(next) nnext=next->next;
        }
        cur=newhead->next;
        delete newhead;
        return cur;
    }
};

注意：
1.开头判断传入链表是否为空，或者第二个节点是否为空，避免创建辅助四节点中后两个节点访问空指针的情况。根据题意只要不是两两交换就直接返回
2.注意循环条件判断，要奇偶数情况都满足才行
3.交换节点后，更新节点，要注意修改后新节点的指针链接关系

三. (143.) 重排链表

算法原理：

找中间节点时要分奇偶数情况讨论，从慢指针位置分离链表还是从慢指针下一位置，对于两种方法其实都满足题意。
但如果逆序第二个链表时采取头插法时最好采用慢指针下一个位置来分离链表，这样才能将slow->next置空，分离两个链表。若采用slow指针当前位置，要增加一个虚拟头节点才能正确分离链表。
画图分析！！

class Solution {
public:
    void reorderList(ListNode* head) {
        //判断边界条件
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr) return;
        //1.找到链表中间节点
        ListNode*left=head,*right=head;
        while(right&&right->next)
        {
            left=left->next;
            right=right->next->next;
        }
        //2.逆置后半部分链表，left->next指针为中间节点
        ListNode*newhead=new ListNode(0);
        ListNode*cur=left->next;
        //newhead->next=cur;虚拟头结点初始化要置空，否则造成循环问题
        left->next=nullptr;//分离前半部分链表
       // ListNode*next=cur->next;
        while(cur)
        {//头插法
            ListNode*next=cur->next;
            cur->next=newhead->next;
             newhead->next=cur;
            cur=next;//更新遍历指针
        }
        //3.合并两个链表
        ListNode*prev=head,*cur2=newhead->next;
        ListNode*head2=new ListNode(0);
        ListNode*nhead=head2;//防止head2节点释放掉后非法访问，合并后链表的头结点不能被释放
        while(prev||cur2)
        {
            //先合共第一个链表的节点，每次合并一个交替进行
            if(prev)nhead->next=prev,prev=prev->next,nhead=nhead->next;
            if(cur2) nhead->next=cur2,cur2=cur2->next,nhead=nhead->next;
        }
        delete newhead;
        delete head2;                       
    }
};

四. (23.) 合并 K 个升序链表

• 解法1：利用优先级队列+小根堆做优化

为每一个链表创建指针来遍历，先将所有指针放入小根堆中，创建虚拟头节点来链接合并后的链表，每次取堆顶元素链接，完后pop掉再放入原堆顶元素所指向的下一个节点，直到为空。
注意创建小跟堆时，因为自定义类型，所以要手动写一个节点的比较函数

class Solution {
    struct cmp{
        bool operator()(const ListNode* x,const ListNode*y){
            return x->val > y->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        //将所有头节点放入小根堆中
        for(auto l:lists)
        {
            if(l) heap.push(l);//不为空才加入，否则cmp时会报错
        }
        //合并操作
        ListNode*newhead=new ListNode(0);
        ListNode*prev=newhead;
        while(!heap.empty())
        {
            ListNode*t=heap.top();
            prev->next=t;
            prev=t;//更新头节点位置
            heap.pop();
            if(t->next) heap.push(t->next);
        }
        prev=newhead->next;
        delete newhead;
        return prev;
    }
};

• 解法2：递归

由于每一个链表已经是有序的，只需关注链表数组的排序，所以可以用递归的方式解决。思路与传统归并排序相同，注意返回值的判断，和节点大小的比较即可

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergesort(lists,0,lists.size()-1);
    }

    ListNode* mergesort(vector<ListNode*>& lists,int left,int right)
    {
        if(left>right) return nullptr;
        if(left==right) return lists[left];//只有一个数组链表直接返回

        int mid=(left+right)>>1;
        //递归处理左右区间
        ListNode*l1=mergesort(lists,left,mid);
        ListNode*l2=mergesort(lists,mid+1,right);

        //合并两个有序链表
        return mergetwolist(l1,l2);
    }

    ListNode*mergetwolist(ListNode*l1,ListNode*l2)
    {//处理了左、右、都，为空的情况
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;
        //归并排序
        ListNode newhead;//在栈上创建空间，避免堆上创建要手动释放
        newhead.next=nullptr;
        ListNode*cur1=l1,*cur2=l2,*ret=&newhead;
        while(cur1&&cur2)
        {
            if(cur1->val>=cur2->val){
                ret=ret->next=cur2;
                cur2=cur2->next;
            }
            else{
                ret=ret->next=cur1;
                cur1=cur1->next;
            }
        }
        //处理多出的链表，注意条件判断是节点是否为空，
        //若像常规归并那样，与l1、l2比较比的是地址大小
        if(cur1) ret->next=cur1;
        if(cur2) ret->next=cur2;

        return newhead.next;
    }
};

五. (25.) K 个⼀组翻转链表

算法原理：
是一个模拟的过程
1.先求出需要逆序多少组：n
2.重复n次，长度为k的链表逆序即可，头插

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur=head;
        int n=0;
        while(cur)
        {
            n++;
            cur=cur->next;
        }
        cur=head;
        int m=n/k;//总共旋转多少次链表
        ListNode *prev,*newhead=new ListNode(0);
        newhead->next=nullptr;
        prev=newhead;
        //旋转链表
        for(int i=0;i<m;i++)
        {
            ListNode*tmp=cur;
           for(int i=0;i<k;i++)
            {//头插，改变链接关系
                ListNode*next=cur->next;
                cur->next=prev->next;
                prev->next=cur;
                //更新节点
                cur=next;     
            }
            prev=tmp;
        }
        //处理剩余节点
        prev->next=cur;
        cur=newhead->next;
        delete newhead;
        return cur;
    }
};