【数据结构与算法】之链表经典算法大集合
本文主要内容是几个关于链表的初级经典算法的分享，都采用Java语言实现，话不多说，立马开始！
注意：以下代码有关链表的算法实现均基于以下链表节点类：
//链表节点类
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; }
}相关教程：
- 有序链表去重（保留重复元素）
- 有序链表去重（不保留重复元素）
- 反转链表
- 链表根据值删除元素
- 删除链表倒数第N个节点
- 数据结构之链表详解
- 递归详解
一、合并两个有序链表
问题描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = []
输出：[]
输入：l1 = [], l2 = [0]
输出：[0]图示：
方法一：双指针二路归并
思路分析：
-
谁小，把谁链给 p，p 和小的都向后平移一位
-
当 p1、p2 有一个为 null，退出循环，把不为 null 的链给 p
p1
|
1 3 8 9 null
p2
|
2 4 null
--------------------------
p
|
s null代码实现：
public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
ListNode s = new ListNode(-1, null);
ListNode p = s;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return s.next;
}方法二：递归
思路分析：
递归函数应该返回
-
更小的那个链表节点，并把它剩余节点与另一个链表再次递归
-
返回之前，更新此节点的 next
//伪代码分析
mergeTwoLists(p1=[1,3,8,9], p2=[2,4]) {
1.next=mergeTwoLists(p1=[3,8,9], p2=[2,4]) {
2.next=mergeTwoLists(p1=[3,8,9], p2=[4]) {
3.next=mergeTwoLists(p1=[8,9], p2=[4]) {
4.next=mergeTwoLists(p1=[8,9], p2=null) {
return [8,9]
}
return 4
}
return 3
}
return 2
}
return 1
}代码实现：
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
//递归调用
if(list1.val < list2.val){
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}else {
list2.next = mergeTwoLists(list1,list2.next);
return list2;
}
}二、合并多个有序链表
问题描述：
给你一个链表数组，每个链表都已经按升序排列。将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：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：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]方法一：递归
思路分析：
这里与合并两个有序链表的思路是一致的，只不过这里采用了分而治之的思想，分：将多个链表不断切分，递归切分为两个有序链表；治：将切分后的两个链表再调用合并两个有序链表的方法，从而实现最终多个有序链表的合并。
代码实现：
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0){
return null;
}
return split(lists,0,lists.length - 1);
}
// 递归切分链表数组,分而治之
// i表示链表数组起始索引，j表示链表数组最后索引
public ListNode split(ListNode[] lists, int i, int j) {
if (i == j) {
return lists[i];
}
int m = (i+j) >>> 1;
return mergeTwoLists(
split(lists,i,m),
split(lists,m+1,j)
);
}
// 合并两个有序链表
public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
ListNode s = new ListNode(-1, null);
ListNode p = s;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return s.next;
}方法二：优先队列
思路分析：
- 创建一个最小堆（优先队列），用于存储所有链表的头节点。
- 每次从堆中取出最小的节点，将其添加到结果链表中，并将该节点的下一个节点添加回堆中。
- 重复步骤2，直到堆为空。
代码实现：
import java.util.PriorityQueue;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) {
heap.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
ListNode smallest = heap.poll();
tail.next = smallest;
tail = smallest;
if (smallest.next != null) {
heap.offer(smallest.next);
}
}
return dummy.next;
}
}三、查找链表中间节点
问题描述：
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
奇数节点时，是中间节点
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 示例 2：
偶数节点时，中间节点是靠右的那个
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点方法一：快慢指针法
思路分析：
快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到链表结尾时，慢指针恰好走到链表的一半
p1p2
|
1 3 5 6 8 null
p1 p2
| |
1 3 5 6 8 null
p1 p2
| |
1 3 5 6 8 null
此时慢指针 p1 指向中间节点
代码实现：
public ListNode middleNode(ListNode head) {
ListNode p1 = head; // 慢指针，中间点
ListNode p2 = head; // 快指针
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}方法二：递归
思路分析：
- 如果链表为空或只有一个节点，直接返回头节点。
- 递归地找到链表后半部分的中间节点。
- 如果后半部分有奇数个节点，返回后半部分的中间节点。
- 如果后半部分有偶数个节点，返回前半部分的最后一个节点。
代码实现：
public ListNode findMiddle(ListNode head) {
return findMiddleRecursive(head, null);
}
private ListNode findMiddleRecursive(ListNode curr, ListNode prev) {
if (curr == null) return prev;
ListNode next = curr.next;
curr.next = prev;
ListNode result = findMiddleRecursive(next, curr);
// 恢复链表结构
curr.next = next;
return result;
}四、回文链表判断
问题描述：
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true示例 2：
输入：head = [1,2]
输出：false方法一：快慢指针和反转链表
思路分析：
整体思路是先找到链表的中间节点，然后反转后半部分链表，最后比较前半部分和反转后的后半部分是否相同，从而判断链表是否为回文链表。
代码实现：
/*
步骤1. 找中间点
步骤2. 中间点后半个链表反转
步骤3. 反转后链表与原链表逐一比较
*/
public boolean isPalindrome(ListNode head) {
ListNode middle = middle(head);
ListNode newHead = reverse(middle);
while (newHead != null) {
if (newHead.val != head.val) {
return false;
}
newHead = newHead.next;
head = head.next;
}
return true;
}
// 反转链表
private ListNode reverse(ListNode o1) {
ListNode n1 = null;
while (o1 != null) {
ListNode o2 = o1.next;
o1.next = n1;
n1 = o1;
o1 = o2;
}
return n1;
}
// 找到中间节点
private ListNode middle(ListNode head) {
ListNode p1 = head; // 慢
ListNode p2 = head; // 快
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}以上代码经过优化后如下：
public boolean isPalindrome(ListNode h1) {
if (h1 == null || h1.next == null) {
return true;
}
ListNode p1 = h1; // 慢指针，中间点
ListNode p2 = h1; // 快指针
ListNode n1 = null; // 新头
ListNode o1 = h1; // 旧头
// 快慢指针找中间点
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
// 反转前半部分
o1.next = n1;
n1 = o1;
o1 = p1;
}
if (p2 != null) { // 节点数为奇数
p1 = p1.next;
}
// 同步比较新头和后半部分
while (n1 != null) {
if (n1.val != p1.val) {
return false;
}
p1 = p1.next;
n1 = n1.next;
}
return true;
}方法二：递归
思路分析：
-
递归到链表的中间：首先，我们需要找到链表的中间节点。这可以通过递归实现，每次递归调用处理链表的后一半，直到链表的长度为1或2，这时我们可以认为到达了中间。
-
递归反转后半部分链表：找到中间节点后，我们继续递归，但是这次是为了反转链表的后半部分。我们可以在到达中间节点后开始反转链表。
-
递归比较前后节点：在反转了后半部分链表之后，我们可以从原始链表的头部和反转后的后半部分的头部开始，递归比较对应节点的值，直到所有节点都被比较完毕或者发现不匹配的节点。
代码实现：
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
/**
* 判断链表是否为回文链表
* @param head 链表的头节点
* @return 是否为回文链表
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 步骤1：找到链表的中间节点
ListNode middle = findMiddle(head);
// 步骤2：反转链表的后半部分
ListNode reversedHead = reverse(middle);
// 步骤3：比较前半部分和反转后的后半部分
return compareTwoLists(head, reversedHead);
}
/**
* 通过快慢指针法找到链表的中间节点
* @param head 链表的头节点
* @return 中间节点
*/
private ListNode findMiddle(ListNode head) {
if (head == null) return null;
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next; // 慢指针每次走一步
fast = fast.next.next; // 快指针每次走两步
}
return slow; // 返回中间节点
}
/**
* 递归反转链表
* @param head 需要反转的链表的头节点
* @return 反转后链表的头节点
*/
private ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverse(head.next);
head.next.next = head; // 将当前节点的下一个节点的next指向当前节点，实现反转
head.next = null; // 将当前节点的next设置为null
return newHead; // 返回新的头节点
}
/**
* 递归比较两个链表是否相等
* @param l1 第一个链表的头节点
* @param l2 第二个链表的头节点
* @return 两个链表是否相等
*/
private boolean compareTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == l2; // 如果两个链表都为空，则认为它们相等
}
if (l1.val != l2.val) {
return false; // 如果当前节点的值不相等，则链表不相等
}
return compareTwoLists(l1.next, l2.next); // 递归比较下一个节点
}
}五、删除链表中间节点
问题描述：
有一个单链表的 head，我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
node前面的所有值顺序相同。node后面的所有值顺序相同。
示例一：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9示例二：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9思路分析：
-
节点值替换：
- 代码的第一行 node.val = node.next.val; 是将待删除节点的值替换为它的下一个节点的值。这样做的目的是为了保留下一个节点的值，因为如果直接删除下一个节点，它的值就会丢失。
-
跳过下一个节点：
- 代码的第二行 node.next = node.next.next; 是将待删除节点的 next 指针指向下一个节点的 next 节点，从而跳过下一个节点。这样，原本的下一个节点（现在值已经被复制到了待删除节点）就从链表中被“删除”了，因为它的前驱节点不再指向它。
这种方法的关键在于，待删除的节点 node 并不是真正的被删除，而是它的值被替换为了下一个节点的值，并且它的 next 指针被调整以跳过下一个节点。这样做的好处是不需要找到待删除节点的前驱节点，可以在任意位置删除节点（只要该节点的下一个节点存在）。
代码实现：
/**
*
* @param node 待删除节点, 已说明肯定不是最后一个节点
*/
public void deleteNode(ListNode node) {
node.val = node.next.val; // 下一个节点值赋值给待"删除"节点
node.next = node.next.next; // 把下一个节点删除
}总结
以上就是关于链表的经典初级算法的集合，希望通过以上的联系，可以让大家更好的掌握关于链表的算法。下期见，谢谢~