【Java-数据结构】Java 链表面试题上 “最后一公里”：解决复杂链表问题的致胜法宝

我的个人主页
我的专栏：Java-数据结构，希望能帮助到大家！！！点赞❤ 收藏❤

引言：
Java链表，看似简单的链式结构，却蕴含着诸多有趣的特性与奥秘，等待我们去挖掘。它就像一个神秘的宝藏迷宫，每一个特性都是隐藏在迷宫深处的珍贵宝藏。链表的环，如同迷宫中的循环通道，一旦进入，便可能陷入无尽的循环；链表节点的唯一性与重复性，仿佛迷宫中的岔路，有的道路独一无二，有的却似曾相识；而链表的长度变化，又如同迷宫的动态扩展与收缩。在接下来的题目中，你将化身为勇敢的探险家，深入链表特性的迷宫，运用你的编程智慧，解开一个个谜题。通过检测链表的环、分析节点的重复性以及精准计算链表长度，你将逐渐揭开链表神秘的面纱，领略数据结构背后的奇妙逻辑。

1. 删除链表中等于给定值 val 的所有节点。移除链表元素

题目视图：

相关代码：

package Demo1_22;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-22 * Time:20:56 */class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; }}class RemoveLinkedListElements { public ListNode removeElements(ListNode head, int val) { // 处理头节点为 null 的情况 while (head!= null && head.val == val) { head = head.next; } ListNode curr = head; // 遍历链表 while (curr!= null && curr.next!= null) { if (curr.next.val == val) { curr.next = curr.next.next; } else { curr = curr.next; } } return head; } public static void main(String[] args) { // 创建链表 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(6); ListNode node4 = new ListNode(3); ListNode node5 = new ListNode(4); ListNode node6 = new ListNode(5); ListNode node7 = new ListNode(6); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; RemoveLinkedListElements solution = new RemoveLinkedListElements(); // 调用 removeElements 方法，删除值为 6 的节点 ListNode newHead = solution.removeElements(node1, 6); // 打印删除节点后的链表元素 ListNode curr = newHead; while (curr!= null) { System.out.print(curr.val + \" \"); curr = curr.next; } }}

2.给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。反转链表

题目视图

题目详解代码：

package Demo1_22;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-23 * Time:18:24 */class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; }}public class ReverseLinkedList { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode nextTemp = current.next; current.next = prev; prev = current; current = nextTemp; } return prev; } public static void main(String[] args) { // 构建链表 1 -> 2 -> 3 -> 4 -> 5 ListNode head = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; ReverseLinkedList solution = new ReverseLinkedList(); ListNode reversedHead = solution.reverseList(head); while (reversedHead != null) { System.out.print(reversedHead.val + \" \"); reversedHead = reversedHead.next; } }}

3.给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。链表的中间节点

题目视图：

题目讲解代码：

package Demo1_22;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-23 * Time:18:30 */class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; }}public class MiddleOfLinkedList { public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } public static void main(String[] args) { // 构建链表 1 -> 2 -> 3 -> 4 -> 5 ListNode head = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; MiddleOfLinkedList solution = new MiddleOfLinkedList(); ListNode middle = solution.middleNode(head); System.out.println(middle.val); } }

4.实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。返回倒数第k个结点的值

题目视图：

题目详解代码：

package Demo1_22;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-23 * Time:18:33 */class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; }}public class FindKthFromEnd { public int findKthFromEnd(ListNode head, int k) { ListNode slow = head; ListNode fast = head; // 先让fast指针前进k步 for (int i = 0; i < k; i++) { if (fast == null) { return -1; // 链表长度小于k，可根据实际情况调整返回值 } fast = fast.next; } // 然后slow和fast同时前进，直到fast到达链表末尾 while (fast != null) { slow = slow.next; fast = fast.next; } return slow.val; } public static void main(String[] args) { // 构建链表 1 -> 2 -> 3 -> 4 -> 5 ListNode head = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; FindKthFromEnd solution = new FindKthFromEnd(); int k = 2; int result = solution.findKthFromEnd(head, k); System.out.println(\"链表中倒数第 \" + k + \" 个节点的值是: \" + result); }}

5.将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

合并两个升序链表

题目视图：

题目详解代码：

package Demo1_22;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-23 * Time:18:36 */class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; }}public class MergeTwoSortedLists { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (list1 != null && list2 != null) { if (list1.val < list2.val) { current.next = list1; list1 = list1.next; } else { current.next = list2; list2 = list2.next; } current = current.next; } if (list1 != null) { current.next = list1; } if (list2 != null) { current.next = list2; } return dummy.next; } public static void main(String[] args) { // 构建链表1: 1 -> 2 -> 4 ListNode list1 = new ListNode(1); list1.next = new ListNode(2); list1.next.next = new ListNode(4); // 构建链表2: 1 -> 3 -> 4 ListNode list2 = new ListNode(1); list2.next = new ListNode(3); list2.next.next = new ListNode(4); MergeTwoSortedLists solution = new MergeTwoSortedLists(); ListNode mergedList = solution.mergeTwoLists(list1, list2); while (mergedList != null) { System.out.print(mergedList.val + \" \"); mergedList = mergedList.next; } }}

今天的链表题目就到这了，还有五到下篇见；