LeetCode+ 21 - 25

合并两个有序链表

算法标签：递归、链表、二路归并

给出两个升序的链表，要把它合并成一个升序的链表，经典的二路归并算法

排序算法 --- 二分查找、快排、归并、分治思想、双重最值问题_小雪菜本菜的博客-CSDN博客

快排、归并、浮点数二分、高精度加、减法_小雪菜本菜的博客-CSDN博客

每次看两个链表剩余的数的第一个数，一开始两个指针指向两个链表的开头

每次比较两个指针指向的元素的大小，把比较小的那个拿到新链表的最后一个位置，新链表一开始为空

题目样例中，一开始两个链表指向的数是一样的，随便拿一个就可以了，可以把第一个链表的第一个节点放到新链表中，把第一个节点删除，然后把第一个链表的指针指向下一个点，下一次再看两个指针指向的数哪个更小，显然第二个指针指向的数比较小，把第二个链表的第一个节点放到新链表中，然后把指针指向下一个位置，以此类推

需要特判头节点 / 头节点可能改变的情况，可以建立一个虚拟头节点避免特判，用两个指针分别指向两个链表最一开始的节点，每次把两个指针较小的那个，拼到新链表的后面，然后把那个指针往后移动一位即可

下面来模拟一下过程

 

 当有一个链表是空的时候，就把另外一个链表拼接到新链表的最后即可

为什么这个做法是正确的呢？

每次找剩余所有数的最小值把它放到新序列的最后，由于两个序列都是有序的，所以每个序列当前剩余的第一个数一定是这个序列的最小值，第一个序列的第一个数是第一个序列的最小值，第二个序列的第一个数是第二个序列的最小值，这两个数的最小值就是整个序列的最小值，每次把两个指针最小的那个拿过来就是剩余所有数的最小值

算法题一般不考虑内存问题，如果考虑的话，就把虚拟头节点删除就可以了

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //建立一个虚拟头节点  定义一个变量指向虚拟头节点的尾节点 由于每次要在新节点的最后加 需要知道新链表的尾节点是谁
        auto dummy = new ListNode(-1),tail = dummy;
        //遍历两个链表
        while(list1 && list2) {
            //当两个链表都不为空的时候,每次比较两个链表哪个更小
            if(list1->val < list2->val) {
                //1.如果第一个链表的值更小,就把 list1 指针的值接到新链表的后面 2.更新新链表的尾节点为 list1
                tail = tail->next = list1;
                //第一个链表用了一个点 第一个链表的指针往后移动一位
                list1 = list1->next;
            } else {
                //list2 同理
                tail = tail->next = list2;
                list2 = list2->next;
            }
        }
        //循环结束之后可能有一个链表非空 如果list1非空就把list1接到最后,如果list2非空就把lsit2接到最后
        if(list1) tail->next = list1;
        if(list2) tail->next = list2;
        return dummy->next;
    }
};

括号生成

算法标签：字符串、动态规划、回溯、递归

 

给出 n 个左括号和 n 个右括号，输出所有合法的括号序列的方案，合法的方案是指括号是可以完美匹配的

下面给出合法与不合法的情况

有  n 个左括号和 n 个右括号，在判断的时候，只要保证每一个左括号都能有一个右括号对应就可以

参考第 15 题：

判断一个括号序列是不是合法用栈来判断，如果遇到一个左括号就把它压到栈里面，如果遇到一个右括号就判断和栈顶的左括号是不是匹配的，如果匹配就筛掉

由于这道题目只有 ' ) ' 和 ' ( '，栈顶元素一定是左括号，当前元素一定是右括号，一定匹配。可以发现这道题目不需要判断是否匹配，只需要保证当我们遇到每一个右括号的时候，栈里面一定有左括号就可以了

n 个左括号和 n 个右括号在什么情况下，构成的序列是合法的？

得出以下推论

由于题目给出的左右括号都是 n 个，所以第二个条件一定满足，在生成序列的时候，只要满足第一个条件就可以了

只要满足任意前缀里面 ' ( ' 一定大于等于 ' ) ' 数量即可，我们在遇到一个右括号的时候，栈里面一定有一个左括号和它匹配

拓展：

如果不要求输出所有方案，只要求输出合法括号序列的数量，这个数量是卡特兰数

怎么输出所有方案？

dfs 递归输出所有方案，可以用一棵递归搜索树来考虑

可以一位一位来考虑，一共有 2n 位，从前往后考虑，假设前面已经考虑了一些情况，每次考虑下一位一共可以填哪些情况：要么填左括号，要么填右括号

接下来看一下什么情况可以填左括号？什么情况可以填右括号？

可以发现任意情况下都可以填左括号，只要左括号的数量小于 n 就可以填左括号

填右括号需要注意，右括号的数量需要小于 n，( 任意前缀里面都满足 ' ( ' 一定大于等于 ' ) ' 数量 )

如果要填右括号，需要满足左括号的数量一定要严格大于右括号的数量，如果相等的话，填了右括号之后，前缀里面右括号的数量就更多了

在 dfs 的时候，每次考虑两种情况，只要满足第一个条件，就可以填左括号然后递归，只要满足第二个条件，就可以填右括号然后递归

整个算法的时间复杂度就是方案的数量，也就是卡特兰数，由于最后需要把方案插到 vector 中，最后需要乘一个 2n（每个方案 seq 的长度是 2n）

这两个推论只适用于一类括号

class Solution {
public:
    //定义一个数组记录答案
    vector<string> ans;
    vector<string> generateParenthesis(int n) {
        //一开始左右括号都是0 seq为空
        dfs(n,0,0,"");
        return ans;
    }
    //括号个数 n 当前的括号序列 seq
    void dfs(int n,int lc, int rc,string seq) {
        //当左右括号用完就结束了 加入答案seq
        if(lc == n && rc == n) ans.push_back(seq);
        else {
            //判断是否能加左括号
            if(lc < n) dfs(n,lc + 1,rc,seq + '(');
            //判断是否能加右括号
            if(rc < n && lc > rc) dfs(n,lc,rc + 1,seq + ')');
        }
    }
};

合并K个升序链表

算法标签：链表、分治、堆(优先队列)、归并排序

参考第 21 题，二路归并：给出两个序列，两个指针指向两个序列的开头，每次把两个指针指向的数较小的那个拿过来放到新序列的下一个位置

如果有 k 个序列其实是类似的，假设有 4 个序列，用 4 个指针指向 4 个序列，每次把 4 个指针里面最小的那个拿出来放到新序列的最后就可以了

由于 4 个序列都是升序的，第一个指针指向的数是第一个序列的最小值，第二个指针指向的数是第二个序列的最小值，以此类推，第三个指针指向的数是第三个序列里面的最小值，所以，这 4 个指针的最小值就是这 4 个序列的最小值

怎么从 k 个指针里面取出最小值？

可以用循环来找最小值，假设所有链表的总长度是 n，时间复杂度就是 n × k，每加一个新的元素都要循环 k 次，时间复杂度就是 O( n × k )

可以用一个堆来维护这 k 个指针，每次找最小值的操作就是 O( 1 )，找到最小值之后，把最小值的指针往后移动一位，再插到新链表中，这一步的时间复杂度是 O( logn )，可以用 stl 里面的优先队列，需要传入自定义的比较函数，和 sort 传入比较函数不太一样

/**
 * 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() (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;
        //先把这 k 个链表的头节点插到堆里面去 如果非空就插入节点 注意是把每个链表的头结点的地址push进去了,而不是把整个链表push进去
        for(auto l : lists) if(l) heap.push(l);
        //k 路归并 当堆里面有元素的时候,每次找最小值
        while(heap.size()) {
            //每次取出堆顶元素
            auto t = heap.top();
            //然后把堆顶元素删掉
            heap.pop();
            //把当前节点插到尾节点的后面 插完之后,t 变成新的尾节点再把尾节点更新一下即可
            tail = tail->next = t;
            //如果 t 有下一个节点,就把下一个节点插到堆里面 相当于把指针往后移动一位
            if(t->next) heap.push(t->next);
        }
        return dummy->next;
    }
};

为什么是重载小括号？ 

因为STL容器在比较的时候用的是结构体的小括号运算符

greater<int>()和less<int>()的使用_chijianxingfeng的博客-CSDN博客_less<int>()

容器里面在比较两个元素的时候会调用 Cmp(a，b)，会返回一个 bool 值，如果 a 应该排在 b 的前面，会返回 true，否则会返回 false，实现比较函数的时候重载了括号，调用的时候就会按照需求来返回

如果 a 小于 b 会放在前面，如果 a 大于 b 会放在后面

如果写小于属于正常的，是大根堆，希望用小根堆，把小于改成大于就可以了

两两交换链表中的节点

算法标签：递归、链表

 

给我们一个链表，需要交换它的所有相邻两个元素，返回交换之后的值，注意：不能修改每个节点中的值，只能改变结构

交换前

交换后

如果有 5 个元素，最后一个元素不用管，得到如下结果

首先可以发现原链表的头节点会改变，需要建立一个虚拟头节点，就不需要考虑头节点会改变的问题

每次枚举的时候应该是枚举相邻两个节点

两个指针分别指向原链表的第一个点和第一个点的下一个点

由于头节点会改变，先建立一个虚拟头节点

 

需要交换 1 和 2 这两个节点，希望它变成 2 和 1

 

接下来看一下具体怎么操作？

首先需要多一个指针指向虚拟头节点

①将虚拟头节点的 next 指针指向 2

②将 2 的 next 指针改成指向 1

 

③将 1 的 next 指针改成指向 3

 

④将指向虚拟头节点的指针指向 1

⑤下一步需要交换的元素为 1→next 和 1→next→next，第一步将 1 的 next 指针改成指向 4，第二步将 4 的 next 指针改成指向 3，第 3 步将 3 的 next 指针改成指向空

在枚举的时候，每次指针指向的位置是要交换的相邻两个元素的前一个位置，如果要交换 1 和 2，指针指向的应该是 1 前面那个位置，要交换 3 和 4，指针指向的应该是 3 前面那个位置

注意顺序：交换之后，如果先改变 2 的话，2 的 next 指针 3 就找不到了

 

/**
 * 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) {
        //建立一个虚拟头节点 让虚拟头节点的 next 指针指向真正的头节点
        auto dummy = new ListNode(-1); 
        dummy->next = head; 
        //从前往后遍历 p就是交换两个点的前一个点
        for(auto p = dummy;p->next && p->next->next/* 交换两个点存在的时候才需要操作 */;) {
            //先找到要交换的第一个点 再找到要交换的第二个点
            auto a = p->next,b = a->next;
            //将 p->next 从 a 改成指向 b
            p->next = b;
            //将 a->next 改成指向 b->next
            a->next = b-> next;
            //再将 b->next 改成指向 a
            b->next = a;
            //再将 p 指向 a
            p = a;
        }
        return dummy->next;
    }
};

K 个一组翻转链表

算法标签：递归、链表

 

 

类似 24 题，给出一个链表，交换相邻两个元素改为翻转相邻 k 个元素，如果最后剩余的数不足 k 个那它们保持原序

样例如下

原链表为 1、2、3、4、5，k = 3，翻转前 3 个元素，后面两个元素不足 3 个保持原序就可以了

由于头节点可能会改变，为了方便可以先搞一个虚拟头节点，避免特判头节点

搞一个指针每次指向需要交换的 k 个元素的前一个元素，每次需要先判断这个元素后面有没有 k 个元素：直接遍历一遍就可以了，如果不足 k 个，直接 break，如果够 k 个就需要交换这 k 个元素

交换 1、2、3 需要分为 3 个部分来考虑

①将 1、2、3 内部的边反向

先将 1 和 2 反向变成 2 和 1，再将 2 和 3 反向变成 3 和 2

②将前面的连接的部分指向正确的位置

 

③将后面的连接的部分指向正确的位置

接下来看一下如何实现以上步骤

翻转内部节点：用一个指针指向第一个元素，第二个指针指向第二个元素

每次用两个指针指向相邻两个元素，将第二个指针本来指向下一个元素改成指向前一个元素

然后把这两个指针向后错一位，重复以上步骤即可

细节

如果把第二个指针指向的指针改成指向前一个，改完之后，下一个元素就找不到了，需要先把下一个元素存储下来

刚刚两个指针会重复 k - 1 次，最终到达 3 和 4 的位置

 让虚拟头节点指向刚刚遍历的第一个指针 3，让虚拟头节点的 next 指针 1 指向刚刚遍历的第二个指针 4

结束之后，让 p 指向下一组的前一个元素 c

这里面的每个元素只会遍历常数次，时间复杂度是线性的，两个 for 循环，一个遍历 n 次，一共遍历 2n 次，时间复杂度为 O( 2n )

/**
 * 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) {
        //定义一个虚拟头节点
        auto dummy = new ListNode(-1);
        dummy->next = head;
        //从虚拟头节点开始遍历整个链表 先遍历一遍 p 后面够不够 k 个元素
        for(auto p = dummy;;) {
            //往后面跳 k 步
            auto q = p;
            //从 p 开始往后跳 k 步元素是不是空就可以了 每次 q 往后跳一步
            for(int i = 0;i < k && q/* 需要保证 q 不是空节点 */;i++) q = q->next;
            //如果跳 k 步后为空说明不足 k 位元素,如果不为空就说明至少有 k 位元素
            if(!q) break;
            //首先定义两个节点 一开始,a 指向每一组的第一个元素,b 指向 a 的下一个元素
            auto a = p ->next,b = a->next; 
            //一共要交换 k - 1 个相邻的位置 
            for(int i = 0;i < k - 1/* 一共要交换 k - 1 条边 */;i++ ) {
                //需要先把 b 的 next 指针存储下来
                auto c = b->next;
                //让 b->next 指向 a
                b->next = a;
                //让 a 跳到 b 的位置,让 b 跳到 c 的位置
                a = b,b = c;
            }
            //以上就把 k 个节点内部的边反向
            //存储 c
            auto c = p->next;
            //让 p 的 next 指针指向 a,让 c 的 next 指针指向 b
            p->next = a,c->next = b;
            //最后让 p 跳到 c 的位置
            p = c;
        }
        //返回虚拟头节点的下一个位置 也就是新的头节点
        return dummy->next;
    }
};