21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

递归

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1==nullptr) return l2; if(l2==nullptr) return l1; if(l1->val<=l2->val){ l1->next=mergeTwoLists(l1->next,l2); return l1; } l2->next=mergeTwoLists(l1,l2->next); return l2; } };

2路归并

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { auto res=new ListNode(-1),tmp=res; while(l1 && l2){ if(l1->val<l2->val){ tmp->next=l1; l1=l1->next; }else{ tmp->next=l2; l2=l2->next; } tmp=tmp->next; } if(l1) tmp->next=l1; if(l2) tmp->next=l2; return res->next; } };

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3 输出：[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

dfs

分析 括号匹配问题的两个准则 1 在任意前缀中 做括号的数目严格大于右括号 2 左括号数目和有哦括号数目相同

class Solution { public: vector<string> res; void dfs(int n,int lc,int rc,string path){ if(lc==n && rc==n) res.push_back(path); else{ if(lc<n) dfs(n,lc+1,rc,path+"("); if(rc<n && lc>rc) dfs(n,lc,rc+1,path+")"); } } vector<string> generateParenthesis(int n) { dfs(n,0,0,""); return res; } };

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

2路归并

算法描述 使用小根堆来维护所有链表头节点中的最小值 将他插入结果链表即可 冷知识: 此处需要自定义比较函数 就写一个Cmp结构体 重载() 然后由于是小根堆 就是a->val>b->val了

class Solution { public: struct Cmp{ bool operator()(ListNode* a,ListNode* b){ return a->val>b->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*,vector<ListNode*>,Cmp> heap; auto dummy=new ListNode(-1),tail=dummy; for(auto l:lists) if(l) heap.push(l); while(heap.size()){ auto t=heap.top(); heap.pop(); tail->next=t; tail=tail->next; if(t->next) heap.push(t->next); } return dummy->next; } };

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

给定 1->2->3->4, 你应该返回 2->1->4->3.

递归

class Solution { public: ListNode* swapPairs(ListNode* head) { if(head==nullptr || head->next==nullptr) return head; auto first=head; auto second=head->next; first->next=swapPairs(second->next); second->next=first; return second; } };

迭代

class Solution { public: ListNode* swapPairs(ListNode* head) { auto dummy=new ListNode(-1); dummy->next=head; auto preNode=dummy; while(head!=nullptr && head->next!=nullptr){ auto firstNode=head,secondNode=head->next; firstNode->next=secondNode->next; secondNode->next=firstNode; preNode->next=secondNode; preNode=firstNode; head=firstNode->next; } return dummy->next; } };

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5

迭代

算法描述: 先判断是否存在k个节点 然后翻转这k个节点 然后处理好头和尾

class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { auto dummy=new ListNode(-1); dummy->next=head; for(auto p=dummy;;){ //判断是否存在k个节点 auto q=p; for(int i=0;i<k && q!=nullptr;i++) q=q->next; if(q==nullptr) break; //翻转这k个节点，k-1次两两交换 auto a=p->next,b=a->next; for(int i=0;i<k-1;i++){ auto c=b->next; b->next=a; a=b,b=c; } //处理头和尾 auto c=p->next; //c是反转之后的k个节点的最后一个节点 翻转之前的第一个节点 p->next=a,c->next=b;//因为结束前面的k个节点的翻转之后 a指向翻转之后的k个节点的第一个节点 也是翻转之前的最后一个节点 b指向下一组的第一个节点 p=c; } return dummy->next; } };