1.链表常用技巧和操作总结

一、常用技巧：1.画图--->直观形象，便于我们理解。2.引入虚拟头结点--->便于处理边界情况，方便我们对链表操作。3.不要吝啬空间，大胆去定义变量。比如：

来一个变量一定义就不用考虑连接次序了，反正可以找到。4.快慢双指针：判环，找链表中环的入口，找到链表中倒数第N个节点。二、链表中的常用操作：1.创建一个新节点new。2.尾插。3.头插。

2.两数相加

2. 两数相加 - 力扣（LeetCode）https://leetcode.cn/problems/add-two-numbers/description/这道题按逆序的方式存储其实是为了方便我们，因为两数相加：

先加个位，逆序存刚好先加第一位。这道题解法是模拟两数相加过程即可，先创一个虚拟头节点，目的是连最终的结果，这样算出来直接连就可以了：

相加时用一个变量t来标记进位。然后定义两个指针模拟加法：

cur1不为空把数加t上，cur2不为空把数加t上，然后t变成了7，同时cur1和cur2右移。然后把t的个位提取出来，new一个节点把值放进去，然后把个位干了，不断重复：

为空时就不管了。下面来实现(两指针走完t里可能依然有进位)：

3.两两交换链表中的结点

24. 两两交换链表中的节点 - 力扣（LeetCode）https://leetcode.cn/problems/swap-nodes-in-pairs/这用迭代方法来解决：

这引入一个虚拟头节点，不加头节点前两个节点交换完后和后面两个节点交换完逻辑是不一样的。因为后面节点换完后前面有节点，还得让前面节点指向交换后的，而前面两个换完前面没节点：

怎么交换？来四个变量，因为两个交换涉及四个节点：

根据交换后看，让prev的next指向next，让next的next指向cur，让cur的next指向nnext。换完后让指针位置这样指向：

进行下一次交换。只要cur/next(单数双数)有一个为空终止循环：

下面实现：

4.重排链表

143. 重排链表 - 力扣（LeetCode）https://leetcode.cn/problems/reorder-list/description/解法是模拟，根据题目要求重排链表就可以。重排后是这样的结果：

它特别像把两个链表按照一定顺序合并起来，合并顺序是先连第一个链表头节点1，再连第二个链表头节点4，然后继续连第一个链表头节点2，再连第二个链表头节点3。这两个链表正好是：第一个是原链表前半部分，第二个是原链表后半部分再逆序一下。因此本题策略是：1.找到原链表的中间节点。2.把后面的部分逆序。3.合并两个链表：

下面来实现，考虑slow落点，单数偶数的情况：

两种情况开始逆序都可以，头插法逆序推荐第一种，因为若从slow逆序位置前一个和slow指向的断不开，有可能会出现意想不到的错误：

最终要成两个链表，第一种把slow的next置空就可以分为两个链表(第一种策略前半部分长，所以考虑cur1不为空)：

5.合并K个升序链表

23. 合并 K 个升序链表 - 力扣（LeetCode）https://leetcode.cn/problems/merge-k-sorted-lists/description/题目就是给了我们若干个升序链表，最终让我们把这些链表合并到一起变成一个升序的链表返回。先说一下解法一：暴力解法。我们以前学过合并两个有序链表的解法，现在有k个链表：

先让前两个合并形成一个新的链表，然后拿新的链表和下面的链表继续合并，这样一直下去：

这样整个链表就完成了合并。这里时间复杂度怎么看呢？假设每个链表的平均长度为n，有k个链表，这样第一个链表最终会和下面链表合并过，合并k-1次；第二个链表也会和下面链表合并过，合并k-2次：

整体的时间复杂度就是这样：

下面想一个更优的解法，利用优先级队列做优化，我们先来想想之前的解法怎么做优化：

我们仿照合并2个有序链表的逻辑先定义k个指针：

把这三个指针中较小的那个位置先放到虚拟头结点的后面，放完后指针右移继续下一次比较：

这个算法时间复杂度就是一个O(n*k)。但这是理想的时间复杂度，因为我们还要找出谁是k个指针指向的结点中较小的那一个，此时就要利用优先级队列。我们的操作是先弄一个小根堆，先把这k个结点丢到小跟堆里面，堆顶的元素就是要连到newhead的那个结点，连完后让下一个位置继续进入小根堆：

整个链表按这样的逻辑走完就合并完毕了，当某个链表走到空这个链表就不进入了。小根堆里有k个元素，增删查改时间复杂度是logk，一共修改n*k个，所以时间复杂度是O(n*k*logk)。下面来编写代码：

6.K个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-nodes-in-k-group/description/题目给了我们一个链表，然后给了我们一个数字k，让我们k个一组的来翻转链表，也就是逆序。若某一部分不够k个，就不翻转那一部分。下面来解决这个问题，这个题的解法就是模拟：

这里模拟的策略是这样：1.先求出需要逆序多少组：n。2.重复n次长度为k的链表的逆序即可。比如上面的示例中，需要逆序2组。这里先求出需要多少组，目的是为了处理后面不逆序的情况。怎么统计呢？仅需遍历链表一次求出链表的结点有n个，然后n=n/3就是需要逆序的组数。然后进行第二步，用头插法逆序，头插时候创建一个新的结点head：

然后把链表头插到结点的后面。从cur位置开始头插，next记录下一个位置：

先头插1，然后cur右移；遍历到2把2头插；遍历到3的时候把3头插：

下面需要头插下一组结点了，下一组结点不是放到head的后面，而是放到1的后面。所以头插的时候需要有一个变量tmp去记录1的位置：

这个1正好是刚开始循环进入的时候插入的结点，所以每次循环进入标记一下循环的第一个位置，把k个结点循环完后下次头插到1的位置：

下一组开始tmp(标记从哪个结点头插)标记4，然后cur从4开始向后遍历，然后再更新prev(每次逆序要头插的结点)的位置：

剩下的链表原封不动的放过去就可以了。下面来实现(n*k是结点个数，O(N))：