本文主要内容是几个关于链表的初级经典算法的分享，都采用Java语言实现，话不多说，立马开始！
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; }
}相关教程：
一、合并两个有序链表
问题描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：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
java">p1
|
1 3 8 9 nullp2
|
2 4 null--------------------------p
|
s null代码实现：
java">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;
}方法二：递归
思路分析：
递归函数应该返回
java">//伪代码分析
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
}代码实现：
java">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;}}二、合并多个有序链表
问题描述：
给你一个链表数组，每个链表都已经按升序排列。将所有链表合并到一个升序链表中，返回合并后的链表。
java">示例 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 = [[]]
输出：[]方法一：递归
思路分析：
这里与合并两个有序链表的思路是一致的，只不过这里采用了分而治之的思想，分：将多个链表不断切分，递归切分为两个有序链表；治：将切分后的两个链表再调用合并两个有序链表的方法，从而实现最终多个有序链表的合并。
代码实现：
java"> 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;}方法二：优先队列
思路分析：
代码实现：
java">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：
java">奇数节点时，是中间节点
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 示例 2：
java">偶数节点时，中间节点是靠右的那个
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点方法一：快慢指针法
思路分析：
快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到链表结尾时，慢指针恰好走到链表的一半
java"> p1p2|1 3 5 6 8 nullp1 p2| |1 3 5 6 8 nullp1 p2| |1 3 5 6 8 null此时慢指针 p1 指向中间节点
代码实现：
java">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;
}方法二：递归
思路分析：
代码实现：
java"> 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方法一：快慢指针和反转链表
思路分析：
整体思路是先找到链表的中间节点，然后反转后半部分链表，最后比较前半部分和反转后的后半部分是否相同，从而判断链表是否为回文链表。
代码实现：
java">/*步骤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;
}以上代码经过优化后如下：
java">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，这时我们可以认为到达了中间。
-
递归反转后半部分链表：找到中间节点后，我们继续递归，但是这次是为了反转链表的后半部分。我们可以在到达中间节点后开始反转链表。
-
递归比较前后节点：在反转了后半部分链表之后，我们可以从原始链表的头部和反转后的后半部分的头部开始，递归比较对应节点的值，直到所有节点都被比较完毕或者发现不匹配的节点。
代码实现：
java">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设置为nullreturn 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 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
示例一：
java">输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9示例二：
java">输入：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 指针被调整以跳过下一个节点。这样做的好处是不需要找到待删除节点的前驱节点，可以在任意位置删除节点（只要该节点的下一个节点存在）。
代码实现：
java"> /**** @param node 待删除节点, 已说明肯定不是最后一个节点*/public void deleteNode(ListNode node) {node.val = node.next.val; // 下一个节点值赋值给待"删除"节点node.next = node.next.next; // 把下一个节点删除}
