链表leetcode-1
目录
1.常用技巧
1.1引入虚拟头结点
1.2对于变量，不要太吝啬，可以多定义，方便处理
1.3快慢双指针
2.例题
2.1两数相加
2.2两两交换链表中的节点
2.3重排链表
2.4合并K个升序链表
2.5K个一组翻转链表
1.常用技巧
1.1引入虚拟头结点
可以方便处理边界情况（因为有些题链表提供的是NULL，如果直接引用会报错，如果是循环链表，没有头结点，题目没有其他条件，就很难判断头尾）
方便对链表操作
1.2对于变量，不要太吝啬，可以多定义，方便处理
1.3快慢双指针
可以用于判环，找链表中环的入口，找链表中倒数第N个节点
关于这方面，可以看我这篇文章
链表（c语言版）-CSDN博客
链表的操作无非就是new一个新节点，尾插或头插，或中间插入，或删除。
头插常用于逆序链表
2.例题
2.1两数相加
2. 两数相加 - 力扣（LeetCode）
这题是给的逆序，因为两数相加是从低位开始加，所以反而方便我们操作了。
只要做模拟即可。
利用一个虚拟头结点和尾指针，模拟加法。
下面是我看到题目马上就写出来的，看起来比较繁琐，但是思路比较清晰
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int jw=0; ListNode*ans=new ListNode(-1);//头结点 ListNode*tail=ans;//尾指针 while(l1&&l2)//先处理两边都有数 { int x=l1->val+l2->val; if(jw)x++,jw=0; if(x>=10)jw++,x-=10; ListNode *tmp=new ListNode(x); tail->next=tmp; tail=tmp; l1=l1->next; l2=l2->next; } while(l1)//处理单个 { int x=l1->val; if(jw)x++,jw=0; if(x>=10)jw++,x-=10; ListNode *tmp=new ListNode(x); tail->next=tmp; tail=tmp; l1=l1->next; } while(l2)//处理单个 { int x=l2->val; if(jw)x++,jw=0; if(x>=10)jw++,x-=10; ListNode *tmp=new ListNode(x); tail->next=tmp; tail=tmp; l2=l2->next; } while(jw)//处理多的进位 { ListNode *tmp=new ListNode(1); tail->next=tmp; tail=tmp; jw--; } return ans->next; } };接下来这个版本是优化过，时间复杂度没区别，代码看起来比较简洁
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode*ans=new ListNode(-1); int x=0; ListNode*tail=ans; while(l1||l2||x) { if(l1) { x+=l1->val; l1=l1->next; } if(l2) { x+=l2->val; l2=l2->next; } tail->next=new ListNode(x%10); x/=10; tail=tail->next; } tail=ans->next; delete ans; return tail; } };2.2两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣（LeetCode）
下面的版本是我挺早写的
思路就是利用递归，比如第一个节点的时候，会把第三个节点开始交换后的头结点返回。
然后将第一个节点和第二个节点交换，并把原第一个节点的next指向上面返回的节点。
class Solution { public: ListNode* swapPairs(ListNode* head) { if(head==nullptr||head->next==nullptr)return head; //因为当前的一对，只有第一个是非NULL节点，第二个节点是NULL，或者第一个节点就是NULL。 //说明不能进行交换，直接返回第一个节点即可。 ListNode*tmp=swapPairs(head->next->next); ListNode*ret=head->next; head->next->next=head; head->next=tmp; return ret; } };接下来是迭代循坏的版本。稍显复杂
class Solution { public: ListNode* swapPairs(ListNode* head) { if(head==nullptr||head->next==nullptr)return head;//可能只有1一个节点或没有节点 ListNode *newhead=new ListNode(0);//虚拟头结点 newhead->next=head; ListNode*prev=newhead;//前驱指针 ListNode*cur=head;//当前指针 ListNode*next=head->next;//当前的下一个指针 ListNode*nnext=head->next->next;//当前的下一个的下一个指针 while(cur&&next)//只要cur或next其中之一为空，就说明不用交换了。 { prev->next=next; next->next=cur; cur->next=nnext; prev=cur; cur=nnext; if(cur)next=nnext->next;//注意原先的nnext可能为空 if(next)nnext=next->next;//注意，原先的nnext的下一个指针可能为空 } cur=newhead->next; delete newhead; return cur; } };2.3重排链表
143. 重排链表 - 力扣（LeetCode）
在写这题前，可以先写
876. 链表的中间结点 - 力扣（LeetCode）
206. 反转链表 - 力扣（LeetCode）
21. 合并两个有序链表 - 力扣（LeetCode）
链表（c语言版）-CSDN博客 这篇文章有反转和中间节点。
关于合并有序链表，可以参考合并有序数组，思路没区别
本题的一个思路，就是上面三题的结合
class Solution { public: void reorderList(ListNode* head) { if(head==nullptr||head->next==nullptr)return;//考虑只有1个节点或没有节点 //快慢指针查找中间节点 ListNode*fast=head,*slow=head; ListNode*prev=nullptr; while(fast&&fast->next) { prev=slow; slow=slow->next; fast=fast->next->next; } prev->next=nullptr;//注意断开链表起始位置和slow开始的部分 //开始反转slow开始的部分 ListNode*cur=slow,*next=slow->next,*newl2=nullptr,*newl1=head; prev=nullptr; while(cur) { if(cur->next==nullptr)newl2=cur; cur->next=prev; prev=cur; cur=next; if(cur)next=next->next; } //开始合并两个有序链表 ListNode*rethead=nullptr; ListNode*rettail=nullptr; ListNode*cur1=newl1,*cur2=newl2; while(cur1||cur2) { if(cur1) { if(rethead==nullptr) { rethead=rettail=cur1; } else { rettail->next=cur1; rettail=rettail->next; } cur1=cur1->next; } if(cur2) { if(rethead==nullptr) { rethead=rettail=cur2; } else { rettail->next=cur2; rettail=rettail->next; } cur2=cur2->next; } } } };2.4合并K个升序链表
23. 合并 K 个升序链表 - 力扣（LeetCode）
本题有3个思路，第一个思路是暴力，我只在这文字描述，不写了，n^3复杂度，铁出事
暴力思路很简单，就是挑2个链表，进行合并两个有序链表的操作，然后把合并出来的链表，再跟剩下的其中一个链表继续重复操作。直到剩下链表都被合并进去了。
思路2，利用优先队列。假设有k个链表，平均n个节点，每次丢入优先队列都会经历一次log k的操作。所以复杂度O(nk log k)
class Solution { public: //重载下指针的比较，方便优先队列自动排序 struct kp { bool operator()(const ListNode*l1,const ListNode*l2) const { return l1->val>l2->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, kp>q; int k = lists.size(); //返回的链表头结点和尾节点 ListNode* rethead = nullptr, *rettail = nullptr; //把链表数组的每个非空头结点放入队列。 for(int i=0;i<k;i++) { if(lists[i])q.push(lists[i]); } while (!q.empty()) { auto tmp = q.top(); q.pop(); //插入返回的链表 if (rethead == nullptr)rethead = rettail = tmp; else { rettail->next = tmp; rettail = rettail->next; } //放入队列 if (tmp->next != nullptr) { q.push(tmp->next); } } return rethead; } };思路3，归并，跟归并排序思路一致，每个链表单独都是一个有序的，每次合并就是把两个有序的链表合并。
每个链表要经历log k次的合并，而一共有k个链表，平均n个节点。复杂度就是n k log k
class Solution { public: ListNode*merge(vector<ListNode*>&lists,int l,int r) { if(l>r)return NULL; if(l==r)return lists[l]; int mid=l+(r-l)/2; ListNode*head1=merge(lists,l,mid); ListNode*head2=merge(lists,mid+1,r); ListNode*ret=NULL,*retil=NULL; //合并两个有序链表 while(head1&&head2) { if(head1->val<head2->val) { if(ret==NULL) { ret=retil=head1; } else { retil->next=head1; retil=retil->next; } head1=head1->next; } else { if(ret==NULL) { ret=retil=head2; } else { retil->next=head2; retil=retil->next; } head2=head2->next; } } while(head1) { if(ret==NULL) { ret=retil=head1; } else { retil->next=head1; retil=retil->next; } head1=head1->next; } while(head2) { if(ret==NULL) { ret=retil=head2; } else { retil->next=head2; retil=retil->next; } head2=head2->next; } return ret; } ListNode* mergeKLists(vector<ListNode*>& lists) { srand(time(NULL)); return merge(lists,0,lists.size()-1); } };2.5K个一组翻转链表
25. K 个一组翻转链表 - 力扣（LeetCode）
本题思路模拟。先求出要逆序多少组。
然后依次逆序即可。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode*cur=head; int n=0; //先计算链表长度n while(cur) { n++; cur=cur->next; } //然后计算需要多少组逆序 n/=k; //依次开始逆序,利用头插方式 cur=head; ListNode*rethead=new ListNode(0); ListNode*prev=rethead,*next=nullptr,*rettail=rethead; for(int i=0;i<n;i++) { //每次都头插在prev后面。 for(int j=0;j<k;j++) { if(j==0)rettail=cur;//记得更新返回链表的末尾 next=cur->next; cur->next=prev->next; prev->next=cur; cur=next; } prev=rettail;//prev每次都更新成返回链表的末尾即可 } prev->next=cur;//把原链表剩下的内容链接上 head=rethead->next; delete rethead; return head; } };
