1.两数相加2. 两数相加 - 力扣LeetCode这题要搞清楚循环的条件是当进位存在或进位不存在此时是因为还没有开始相加但cur1或cur2还都没有走到终点那么可以写成while(cur1||cur2||t)(t是进位)另外为了方便插入数据需要创建一个头节点还需创建一个指针一直指向新创建的需要返回的链表的尾节点便于插入新的节点两数相加的进位最多是1所以每次循环把t的个位作为新节点的值t/10得到进位代码如下/** * 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* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode*cur1l1,*cur2l2; ListNode* newheadnew ListNode(0); ListNode* prevnewhead; int t0; while(cur1||cur2||t) { if(cur1) { tcur1-val; cur1cur1-next; } if(cur2) { tcur2-val; cur2cur2-next; } prev-nextnew ListNode(t%10); prevprev-next; t/10; } prevnewhead-next; delete newhead; return prev; } };2.两两交换链表中的节点24. 两两交换链表中的节点 - 力扣LeetCode这道题一个比较重要的点是弄明白添加头节点以中间两个元素为交换元素的四个节点为一组做交换因为这样要交换的两个节点两边都有节点是已知的交换的过程中不会断开链表另外还要明确循环结束的条件这个要通过画图来推出当节点个数为偶数时不包括新添加的头结点观察可知临界时只有prev和cur是一定有对应所指位置的所以循环重置顺序时应该先重置prev和cur看此时是否满足循环的条件再重置next和nnext由于prev在前cur在后所以循环条件要先保证prev再保证cur即写成(prev-next!NULLcur-next!NULL)代码如下/** * 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* swapPairs(ListNode* head) { ListNode* newheadnew ListNode(0); newhead-nexthead; ListNode* prevnewhead,*curprev-next; while(prev-next!NULLcur-next!NULL) { ListNode* nextcur-next,*nnextnext-next; prev-nextnext; next-nextcur; cur-nextnnext; prevcur; curnnext; } prevnewhead-next; delete newhead; return prev; } };3.重排链表143. 重排链表 - 力扣LeetCode这道题是多个基础题的结合分成3步①找到链表的中心节点用快慢双指针法②把后面的部分逆序三指针/头插③合并两个链表双指针注意把链表分成前后段后要注意切断前后段逆序的逻辑是把一个节点和其要头插到的两个相连的节点重新关联的过程要搞清楚重新 关联的逻辑另外还有可优化的地方如果是按照上述思路那么为了确定slow的上一个节点需要增设一个变量始终指向slow之前另外由于断开和开始逆序的位置不同对于奇数和偶数的情况要分开写代码但事实上不用对奇偶分开讨论确定逆序开始和断开的位置从slow-next或slow开始逆序得到的结果都是一样的但推荐用slow-next开始逆序因为这样可以直接从slow断开从slow-next开始逆序但如果要从slow开始逆序为了断开前一个要么设一个始终指向前面的变量要么在找中心节点之前在题给链表前连接一个头节点newhead让slow从头节点newhead开始走fast从head开始走这样slow对应的实际上是slow的前一个slow-next对应的是slow从slow断开从slow-next逆序即可最后合并两个链表可以选择创建一个新节点将前后两段的节点依次连接到新节点处也可以设置两个指向cur1和cur2后的指针来记忆cur-next代码如下/** * 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: void reorderList(ListNode* head) { if(head-nextNULL||head-next-nextNULL) return; ListNode* fasthead,*slowhead; while(fast!NULLfast-next!NULL) { fast(fast-next)-next; slowslow-next; } ListNode* prevslow-next; slow-nextNULL; ListNode* newheadnew ListNode(0); while(prev!NULL) { ListNode* nextprev-next; prev-nextnewhead-next; newhead-nextprev; prevnext; } ListNode* cur2newhead-next,*cur1head; while(cur2!NULL) { ListNode* tmp1cur1-next; ListNode* tmp2cur2-next; cur1-nextcur2; cur2-nexttmp1; cur1tmp1; cur2tmp2; } delete newhead; } };4.合并K个升序链表23. 合并 K 个升序链表 - 力扣LeetCode方法一堆取每个链表的头节点入堆创建一个新头节点newhead把堆顶元素取出连接到newhead之后再把堆顶删除此时如果堆顶代表的节点之后还有元素将下一个元素入堆否则一直出堆顶代码如下/** * 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: struct cmp { bool operator()(const ListNode* l1,const ListNode* l2) { return l1-vall2-val; } }; ListNode* mergeKLists(vectorListNode* lists) { priority_queueListNode*,vectorListNode*,cmp heap; for(auto l:lists) if(l) heap.push(l); ListNode* newheadnew ListNode(0); ListNode* tmpnewhead; while(!heap.empty()) { ListNode* theap.top(); tmp-nextt; heap.pop(); tmptmp-next; if(t-next) heap.push(t-next); } ListNode* retnewhead-next; delete newhead; return ret; } };方法二分治即用以前分治的方法去写区别不太大实际上是最小的单元从元素变成了链表排好序的代码如下/** * 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* mergeTowList(ListNode*cur1,ListNode* cur2) { if(cur1nullptr) return cur2; if(cur2nullptr) return cur1; ListNode* newheadnew ListNode(0); ListNode* tmpnewhead; while(cur1cur2) { if(cur1-valcur2-val) { tmp-nextcur1; tmptmp-next; cur1cur1-next; } else { tmp-nextcur2; tmptmp-next; cur2cur2-next; } } if(cur1) { tmp-nextcur1; } if(cur2) { tmp-nextcur2; } tmpnewhead-next; delete newhead; return tmp; } ListNode* merge(vectorListNode* lists,int left,int right) { if(leftright) return lists[left]; if(leftright) return nullptr; int midleft(right-left)/2; ListNode* cur1merge(lists,left,mid); ListNode* cur2merge(lists,mid1,right); return mergeTowList(cur1,cur2); } ListNode* mergeKLists(vectorListNode* lists) { int nlists.size(); return merge(lists,0,n-1); } };暴力解法的时间复杂度是方法一的时间复杂度是方法二的时间复杂度也是5.K个一组翻转链表25. K 个一组翻转链表 - 力扣LeetCode这题的思路其实不难只要弄清要翻转多少组对每组进行K次翻转用头插的方法最后把多余的节点连接起来即可cur遍历链表tmp指向cur下一个prev指向头插的前节点由于每进行一组时需要上一组的头节点作为头插前节点所以在进行一组前先保存好cur出大循环后cur有可能指向NULL刚好是整数组K也有可能指向非NULL还有一些多余的节点此时prev已准备好prev-nextcur返回retnewhead-next代码如下/** * 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* numshead; int n0; while(nums) { n; numsnums-next; } ListNode* newheadnew ListNode(0); ListNode* prevnewhead,*curhead; while(nk) { ListNode* acur; int ik; while(i) { ListNode* tmpcur-next; cur-nextprev-next; prev-nextcur; curtmp; i--; } n-k; preva; } prev-nextcur; ListNode* retnewhead-next; delete newhead; return ret; } };