优选算法的链脉之韵：链表专题

专栏：算法的魔法世界

个人主页：手握风云

目录

一、链表常用技巧和操作总结

二、例题讲解

2.1. 两数相加

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

2.3. 重排链表

2.4. 合并 K 个升序链表

2.5. K 个一组翻转链表

一、链表常用技巧和操作总结

• 常用技巧

1. 画图（非常重要！）：画图直观形象，更有助于我们理解，不至于去访问空节点。
2. 引入虚拟头节点：一般链表相关的算法题，输入的链表头节点就是有效的数据，并且还是单向链表。如果头节点就传入一个null，直接导致程序崩掉。这个虚拟头节点只是起到一个哨兵的作用，它的作用可以帮助我们处理边界情况，也方便对链表进行操作。

   

3. 不要吝啬空间，大胆去定义变量。
4. 快慢双引用。适用于判断链表是否有环、寻找环形链表的入口、以及找链表中倒数第n个节点

• 链表的常用操作

        新建一个链表节点、头插、尾插。

二、例题讲解

2.1. 两数相加

        每个链表表示一个非负整数，数字是逆序存储的，每个节点只能存储一位数字。目标是返回一个新的链表，表示两个输入链表表示的数字的和。需要注意的是，除了数字0之外，这两个数都不会以0开头。

        本题的算法原理就是模拟两数相加的过程即可：从个数开始一次往前相加，当两个数位上的数相加超过10时，再往前进一位。如果说我们不引入虚拟头节点的话，就会面临一种情况：把前两位算出来当作新链表的头节点。当引入虚拟头节点时，就可以直接进行相加的操作。我们定义一个变量t来标记进位，再用两个引用cur1和cur2从头遍历链表，只要两个引用不为空，让两个节点值相加，再让两个引用右移。得到t的值之后，把t的个位提出来，放进新链表中，并保留t的十位数。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode cur1 = l1, cur2 = l2; // 虚拟头节点 ListNode newHead = new ListNode(0); // 方便尾插 ListNode prev = newHead; int t = 0; // 防止第一位是9，当t=1时，还要向前进一位 while (cur1 != null || cur2 != null || t != 0) { // 如果cur1不为空，则将cur1的值加到t上，并将cur1指向下一个节点 if (cur1 != null) { t += cur1.val; cur1 = cur1.next; } // 如果cur2不为空，则将cur2的值加到t上，并将cur2指向下一个节点 if (cur2 != null) { t += cur2.val; cur2 = cur2.next; } prev.next = new ListNode(t % 10); // 将prev指向新插入的节点 prev = prev.next; // 将t除以10的商赋值给t t /= 10; } // 返回虚拟头节点的下一个节点，即新链表的头节点 return newHead.next; }}

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

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

        我们先回顾递归的解法：先对链表的前两个节点进行交换，再把剩下的节点丢进递归方法中，最后把交换后的节点连上递归的节点。
        这里我们需要用模拟迭代的方法来解决本题：如果我们不引入虚拟头节点，那我们前面不需要next引用指向交换后的第二个节点，但后面我们需要让第二个节点指向它后面的节点。如果我们引入虚拟头节点之后，那么所有链表的交换逻辑是一样的。

        我们直接定义4个变量prev、cur、nextO、nextON，我们先将前两个节点进行交换，只需要根据图中的next引用修改指向即可。然后再将后面的节点进行相同的交换操作，这里只需要一个while循环就可以搞定。

        接下来我们需要考虑空引用的情况，如果链表的节点数为偶数时，prev走到最后一个节点时，cur为空了；如果链表的节点数为奇数时，cur走到最后一个节点时，nextO为空。

        完整代码实现：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode swapPairs(ListNode head) { // 如果链表为空或只有一个节点，则直接返回 if (head == null || head.next == null) { return head; } ListNode newHead = new ListNode(0,head); ListNode prev = newHead, cur = prev.next, nextO = cur.next, nextON = nextO.next; // 遍历链表，每次交换cur和nextO的位置 while (cur != null && nextO != null) { prev.next = nextO; nextO.next = cur; cur.next = nextON; prev = cur; cur = nextON; // 如果cur不为空，则将nextO指向cur的下一个节点 if (cur != null) { nextO = cur.next; } // 如果nextO不为空，则将nextON指向nextO的下一个节点 if (nextO != null) { nextON = nextO.next; } } // 返回新链表的头节点 return newHead.next; }}

2.3. 重排链表

        题目要求是将一个给定的单链表 L 重新排列，从形式 L0 → L1 → … → Ln - 1 → Ln 变为 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …。这种重排不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

        本题的思路可以看作是两个链表的合并，先把链表从中间分开，然后将后半部分的链表进行反转，最后进行两个链表的合并。所以我们的核心步骤：1. 找到链表的中间节点；2. 反转后半部分的链表；3. 两个链表的合并。

        找到链表的中间节点：我们使用的是快慢双指针法。快慢指针同时从头节点出发，快指针一次走两步，慢指针一次走一步。如果链表节点数为奇数个，当fast.next为空时，slow所指就是中间节点；如果链表节点数为偶数个，当fast为空时，slow所指就是中间节点。

        反转链表：先将要反转的链表头节点的next引用置为空，再利用头插法将后面的节点依次连接上旧链表的头节点，每次还要将head引用指向新链表的头节点。

        合并两个链表：利用两个引用分别指向链表的头节点，，两个引用一次向后移动

        完整代码实现：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return; } // 先找到链表的中间节点 ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } // slow后面的部分进行翻转 ListNode head2 = new ListNode(0); ListNode cur = slow.next; slow.next = null; while (cur != null) { ListNode curN = cur.next; cur.next = head2.next; head2.next = cur; cur = curN; } // 合并两个链表 ListNode cur1 = head, cur2 = head2.next; ListNode ret = new ListNode(0); ListNode prev = ret; while (cur1 != null) { prev.next = cur1; prev = cur1; cur1 = cur1.next; if (cur2 != null) { prev.next = cur2; prev = cur2; cur2 = cur2.next; } } }}

2.4. 合并 K 个升序链表

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

        我们先来思考暴力解法：先让前两个链表进行有序合并，得到一个新链表，再用新链表与第三个链表进行合并，以此循环，知道合并完最后一个链表。但这种解法的时间复杂度很高，。

        第二种解法：仿照排序算法中的归并排序的分治思想。从lists数组中间分开，让前半部分的链表进行合并，后半部分的链表进行合并，而分开的部分再次进行递归，按照上面的思路再次进行递归，直到lists只有单个元素时，递归结束。此时的时间复杂度为。

        完整代码实现：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); } private ListNode merge(ListNode[] lists, int left, int right) { if (left > right) { return null; } if (left == right) { return lists[left]; } // 计算中间位置 int mid = (left + right) / 2; // 递归合并左半部分链表 ListNode l1 = merge(lists, left, mid); // 递归合并右半部分链表 ListNode l2 = merge(lists, mid + 1, right); return mergeTwoList(l1, l2); } private ListNode mergeTwoList(ListNode l1, ListNode l2) { // 如果l1为空，则返回l2 if (l1 == null) { return l2; } // 如果l2为空，则返回l1 if (l2 == null) { return l1; } ListNode head = new ListNode(0); ListNode cur1 = l1, cur2 = l2, prev = head; // 循环遍历l1和l2，直到其中一个链表为空 while (cur1 != null && cur2 != null) { // 如果l1的节点值小于等于l2的节点值，则将l1的节点连接到新链表的尾部 if (cur1.val <= cur2.val) { prev.next = cur1; prev = cur1; cur1 = cur1.next; // 否则，将l2的节点连接到新链表的尾部 } else { prev.next = cur2; prev = cur2; cur2 = cur2.next; } } // 如果l1不为空，则将l1的剩余节点连接到新链表的尾部 if (cur1 != null) { prev.next = cur1; // 否则，将l2的剩余节点连接到新链表的尾部 } else { prev.next = cur2; } return head.next; }}

2.5. K 个一组翻转链表

        给定一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。如果链表中的节点数不是 k 的整数倍，那么最后剩余的节点保持原有顺序。

        本题虽然是困难标签，但其实考察的还是模拟过程。我们第一步先求出链表的长度，再进行模k的操作，这样就可以得出我们需要反转多少组链表，接着重复n次反转k个节点的操作。反转这部分链表，这里我们使用头插法进行操作。先将cur.next引用指向newHead的next引用，再用newHead的next引用指向cur，为了防止cur后面的节点丢失，我们再用一个next引用记录。头插完一个节点后，接着将cur指向next。当头插完第一组后，下一组的头插是要插在节点1后面，所以我们还需要一个tmp记录下节点1的位置，利用prev再更新到tmp的位置。当我们要头插下一组时，将tmp更新到节点4的位置，保证头插的时候是在节点1的后面。当我们反转完K组之后，原链表剩下的部分，只需连接到新链表的尾部就可以。

        完整代码实现：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode reverseKGroup(ListNode head, int k) { public ListNode reverseKGroup(ListNode head, int k) { // 计算链表长度 int n = 0; ListNode cur = head; while (cur != null) { n++; cur = cur.next; } // 计算需要反转的组数 n /= k; // 创建一个新的头节点 ListNode newHead = new ListNode(0); // prev指向新的头节点 ListNode prev = newHead; // cur指向原链表的头节点 cur = head; // 遍历链表，反转每组k个节点 for (int i = 0; i < n; i++) { // tmp指向当前组的第一个节点 ListNode tmp = cur; // 反转当前组的k个节点 for (int j = 0; j < k; j++) { // next指向当前节点的下一个节点 ListNode next = cur.next; // 将当前节点的next指向prev的next cur.next = prev.next; // 将prev的next指向当前节点 prev.next = cur; // 将cur指向next cur = next; } // prev指向当前组的第一个节点 prev = tmp; } // 将prev的next指向剩余的节点 prev.next = cur; return newHead.next; }}