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

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

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

6.编写代码，以给定值x为基准将链表分割成两部分，所有⼩于x的结点排在⼤于或等于x的结点之前—链表分割

题目视图：

题目详解代码：

// 定义链表节点类class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; }}public class PartitionList { public ListNode partition(ListNode pHead, int x) { // 创建两个虚拟头节点，分别用于存储小于 x 和大于等于 x 的节点 ListNode smallDummy = new ListNode(0); ListNode largeDummy = new ListNode(0); // 分别指向两个新链表的当前节点 ListNode smallTail = smallDummy; ListNode largeTail = largeDummy; // 遍历原链表 ListNode current = pHead; while (current != null) { if (current.val < x) { // 如果当前节点的值小于 x，将其连接到 small 链表的尾部 smallTail.next = current; smallTail = smallTail.next; } else { // 如果当前节点的值大于等于 x，将其连接到 large 链表的尾部 largeTail.next = current; largeTail = largeTail.next; } // 移动到下一个节点 current = current.next; } // 断开 large 链表的尾部，防止出现循环 largeTail.next = null; // 将 small 链表和 large 链表连接起来 smallTail.next = largeDummy.next; // 返回重新排列后的链表的头节点 return smallDummy.next; } public static void main(String[] args) { // 创建测试链表 1 -> 4 -> 3 -> 2 -> 5 -> 2 ListNode head = new ListNode(1); head.next = new ListNode(4); head.next.next = new ListNode(3); head.next.next.next = new ListNode(2); head.next.next.next.next = new ListNode(5); head.next.next.next.next.next = new ListNode(2); PartitionList solution = new PartitionList(); int x = 3; // 调用 partition 方法进行重新排列 ListNode newHead = solution.partition(head, x); // 打印重新排列后的链表 ListNode current = newHead; while (current != null) { System.out.print(current.val + \" \"); current = current.next; } }}

7.链表的回⽂结构。题目链接

题目视图：

题目详解代码：

package Demo1_28;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-28 * Time:20:04 */// 定义链表节点类class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; }}public class PalindromeLinkedList { public boolean isPalindrome(ListNode A) { if (A == null || A.next == null) { return true; } // 步骤 1：找到链表的中间节点 ListNode slow = A; ListNode fast = A; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } // 步骤 2：反转链表的后半部分 ListNode secondHalf = reverseList(slow.next); // 步骤 3：比较链表的前半部分和反转后的后半部分 ListNode p1 = A; ListNode p2 = secondHalf; boolean result = true; while (result && p2 != null) { if (p1.val != p2.val) { result = false; } p1 = p1.next; p2 = p2.next; } // 步骤 4：恢复链表的原始结构 slow.next = reverseList(secondHalf); return result; } // 反转链表的方法 private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } public static void main(String[] args) { // 创建测试链表 1 -> 2 -> 2 -> 1 ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(2); head.next.next.next = new ListNode(1); PalindromeLinkedList solution = new PalindromeLinkedList(); // 调用 isPalindrome 方法判断链表是否为回文结构 boolean isPalindrome = solution.isPalindrome(head); System.out.println(isPalindrome); }}

8.输⼊两个链表，找出它们的第⼀个公共结点。—题目链接

题目视图：

题目详解代码：

package Demo1_28;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-28 * Time:20:08 */// 定义链表节点类class ListNode { int val; ListNode next; // 构造函数，用于初始化节点的值 ListNode(int x) { val = x; next = null; }}public class IntersectionOfTwoLinkedLists { // 查找两个链表相交的起始节点的方法 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 如果其中一个链表为空，直接返回 null if (headA == null || headB == null) { return null; } // 初始化两个指针分别指向两个链表的头节点 ListNode pA = headA; ListNode pB = headB; // 当两个指针不相等时，继续循环 while (pA != pB) { // 如果 pA 到达链表 A 的末尾，将其指向链表 B 的头节点 pA = pA == null ? headB : pA.next; // 如果 pB 到达链表 B 的末尾，将其指向链表 A 的头节点 pB = pB == null ? headA : pB.next; } // 返回相交节点，如果不相交则返回 null return pA; } public static void main(String[] args) { // 创建示例链表 // 链表 A: 1 -> 2 -> 3 -> 6 -> 7 ListNode headA = new ListNode(1); headA.next = new ListNode(2); headA.next.next = new ListNode(3); // 链表 B: 4 -> 5 -> 6 -> 7 ListNode headB = new ListNode(4); headB.next = new ListNode(5); // 创建相交部分 ListNode intersection = new ListNode(6); intersection.next = new ListNode(7); // 连接链表 A 和相交部分 headA.next.next.next = intersection; // 连接链表 B 和相交部分 headB.next.next = intersection; // 创建 IntersectionOfTwoLinkedLists 类的实例 IntersectionOfTwoLinkedLists solution = new IntersectionOfTwoLinkedLists(); // 调用 getIntersectionNode 方法查找相交节点 ListNode result = solution.getIntersectionNode(headA, headB); if (result != null) { System.out.println(\"相交节点的值为: \" + result.val); } else { System.out.println(\"两个链表不相交\"); } }}

9.给你一个链表的头节点 head ，判断链表中是否有环。—题目链接

题目视图：

题目详解代码：

// 定义链表节点类class ListNode { int val; ListNode next; // 构造函数，用于初始化节点的值 ListNode(int x) { val = x; next = null; }}public class LinkedListCycle { // 判断链表是否有环的方法 public boolean hasCycle(ListNode head) { // 如果链表为空或者只有一个节点，肯定没有环 if (head == null || head.next == null) { return false; } // 慢指针，初始指向头节点，每次移动一步 ListNode slow = head; // 快指针，初始指向头节点的下一个节点，每次移动两步 ListNode fast = head.next; // 当慢指针和快指针不相等时，继续循环 while (slow != fast) { // 如果快指针到达链表末尾或者快指针的下一个节点是末尾，说明没有环 if (fast == null || fast.next == null) { return false; } // 慢指针移动一步 slow = slow.next; // 快指针移动两步 fast = fast.next.next; } // 如果跳出循环，说明慢指针和快指针相遇了，链表有环 return true; } public static void main(String[] args) { // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始） ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); // 构建链表连接关系 node1.next = node2; node2.next = node3; node3.next = node4; // 形成环 node4.next = node2; // 创建 LinkedListCycle 类的实例 LinkedListCycle solution = new LinkedListCycle(); // 调用 hasCycle 方法判断链表是否有环 boolean result = solution.hasCycle(node1); System.out.println(\"链表是否有环: \" + result); // 创建无环链表 1 -> 2 -> 3 -> 4 ListNode nodeA = new ListNode(1); ListNode nodeB = new ListNode(2); ListNode nodeC = new ListNode(3); ListNode nodeD = new ListNode(4); // 构建无环链表连接关系 nodeA.next = nodeB; nodeB.next = nodeC; nodeC.next = nodeD; // 再次调用 hasCycle 方法判断无环链表是否有环 result = solution.hasCycle(nodeA); System.out.println(\"链表是否有环: \" + result); }}

10.给定⼀个链表，返回链表开始⼊环的第⼀个节点。 如果链表⽆环，则返回 NULL

—题目链接

题目视图：

题目详解代码：

package Demo1_28;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-28 * Time:20:15 */// 定义链表节点类class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; }}public class LinkedListCycleII { public ListNode detectCycle(ListNode head) { // 如果链表为空或只有一个节点，肯定没有环 if (head == null || head.next == null) { return null; } // 慢指针，初始指向头节点，每次移动一步 ListNode slow = head; // 快指针，初始指向头节点，每次移动两步 ListNode fast = head; boolean hasCycle = false; // 寻找是否有环 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; // 快慢指针相遇，说明有环 if (slow == fast) { hasCycle = true; break; } } // 如果没有环，返回 null if (!hasCycle) { return null; } // 慢指针重新指向头节点 slow = head; // 快慢指针都以每次一步的速度移动，再次相遇的节点就是环的入口节点 while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } public static void main(String[] args) { // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始） ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); // 构建链表连接关系 node1.next = node2; node2.next = node3; node3.next = node4; // 形成环 node4.next = node2; // 创建 LinkedListCycleII 类的实例 LinkedListCycleII solution = new LinkedListCycleII(); // 调用 detectCycle 方法找到环的入口节点 ListNode result = solution.detectCycle(node1); if (result != null) { System.out.println(\"环的入口节点的值为: \" + result.val); } else { System.out.println(\"链表中没有环\"); } // 创建无环链表 1 -> 2 -> 3 -> 4 ListNode nodeA = new ListNode(1); ListNode nodeB = new ListNode(2); ListNode nodeC = new ListNode(3); ListNode nodeD = new ListNode(4); // 构建无环链表连接关系 nodeA.next = nodeB; nodeB.next = nodeC; nodeC.next = nodeD; // 再次调用 detectCycle 方法判断无环链表是否有环 result = solution.detectCycle(nodeA); if (result != null) { System.out.println(\"环的入口节点的值为: \" + result.val); } else { System.out.println(\"链表中没有环\"); } }}

所有的链表题目就分享到着了继续加油❤👍！！！