【Java-数据布局】Java 链外貌试题下 “末了一公里”：解决复杂链表题目的 ...

我的个人主页
我的专栏：Java-数据布局，希望能帮助到各人！！！点赞❤ 收藏❤

   引言：
Java链表，看似简朴的链式布局，却蕴含着诸多有趣的特性与奥秘，等待我们去发掘。它就像一个神秘的宝藏迷宫，每一个特性都是隐蔽在迷宫深处的珍贵宝藏。链表的环，犹如迷宫中的循环通道，一旦进入，便大概陷入无尽的循环；链表节点的唯一性与重复性，仿佛迷宫中的岔路，有的道路独一无二，有的却似曾相识；而链表的长度变革，又犹如迷宫的动态扩展与收缩。在接下来的题目中，你将化身为勇敢的探险家，深入链表特性的迷宫，运用你的编程智慧，解开一个个谜题。通过检测链表的环、分析节点的重复性以及精准计算链表长度，你将徐徐揭开链表神秘的面纱，明白数据布局背后的奥妙逻辑。
  6.编写代码，以给定值x为基准将链表分割成两部分，所有⼩于x的结点排在⼤于或等于x的结点之前—链表分割

   题目视图：

  题目详解代码：

1. // 定义链表节点类
2. class ListNode {
3.     int val;
4.     ListNode next;
5.     ListNode(int x) {
6.         val = x;
7.         next = null;
8.     }
9. }
11. public class PartitionList {
12.     public ListNode partition(ListNode pHead, int x) {
13.         // 创建两个虚拟头节点，分别用于存储小于 x 和大于等于 x 的节点
14.         ListNode smallDummy = new ListNode(0);
15.         ListNode largeDummy = new ListNode(0);
16.         // 分别指向两个新链表的当前节点
17.         ListNode smallTail = smallDummy;
18.         ListNode largeTail = largeDummy;
20.         // 遍历原链表
21.         ListNode current = pHead;
22.         while (current != null) {
23.             if (current.val < x) {
24.                 // 如果当前节点的值小于 x，将其连接到 small 链表的尾部
25.                 smallTail.next = current;
26.                 smallTail = smallTail.next;
27.             } else {
28.                 // 如果当前节点的值大于等于 x，将其连接到 large 链表的尾部
29.                 largeTail.next = current;
30.                 largeTail = largeTail.next;
31.             }
32.             // 移动到下一个节点
33.             current = current.next;
34.         }
36.         // 断开 large 链表的尾部，防止出现循环
37.         largeTail.next = null;
38.         // 将 small 链表和 large 链表连接起来
39.         smallTail.next = largeDummy.next;
41.         // 返回重新排列后的链表的头节点
42.         return smallDummy.next;
43.     }
45.     public static void main(String[] args) {
46.         // 创建测试链表 1 -> 4 -> 3 -> 2 -> 5 -> 2
47.         ListNode head = new ListNode(1);
48.         head.next = new ListNode(4);
49.         head.next.next = new ListNode(3);
50.         head.next.next.next = new ListNode(2);
51.         head.next.next.next.next = new ListNode(5);
52.         head.next.next.next.next.next = new ListNode(2);
54.         PartitionList solution = new PartitionList();
55.         int x = 3;
56.         // 调用 partition 方法进行重新排列
57.         ListNode newHead = solution.partition(head, x);
59.         // 打印重新排列后的链表
60.         ListNode current = newHead;
61.         while (current != null) {
62.             System.out.print(current.val + " ");
63.             current = current.next;
64.         }
65.     }
66. }

复制代码

7.链表的回⽂布局。题目链接

   题目视图：

  题目详解代码：

1. package Demo1_28;
3. /**
4. * Created with IntelliJ IDEA.
5. * Description:
6. * User：Lenovo
7. * Date:2025-01-28
8. * Time:20:04
9. */
10. // 定义链表节点类
11. class ListNode {
12.     int val;
13.     ListNode next;
14.     ListNode(int x) {
15.         val = x;
16.         next = null;
17.     }
18. }
20. public class PalindromeLinkedList {
21.     public boolean isPalindrome(ListNode A) {
22.         if (A == null || A.next == null) {
23.             return true;
24.         }
25.         // 步骤 1：找到链表的中间节点
26.         ListNode slow = A;
27.         ListNode fast = A;
28.         while (fast.next != null && fast.next.next != null) {
29.             slow = slow.next;
30.             fast = fast.next.next;
31.         }
32.         // 步骤 2：反转链表的后半部分
33.         ListNode secondHalf = reverseList(slow.next);
34.         // 步骤 3：比较链表的前半部分和反转后的后半部分
35.         ListNode p1 = A;
36.         ListNode p2 = secondHalf;
37.         boolean result = true;
38.         while (result && p2 != null) {
39.             if (p1.val != p2.val) {
40.                 result = false;
41.             }
42.             p1 = p1.next;
43.             p2 = p2.next;
44.         }
45.         // 步骤 4：恢复链表的原始结构
46.         slow.next = reverseList(secondHalf);
47.         return result;
48.     }
50.     // 反转链表的方法
51.     private ListNode reverseList(ListNode head) {
52.         ListNode prev = null;
53.         ListNode curr = head;
54.         while (curr != null) {
55.             ListNode nextTemp = curr.next;
56.             curr.next = prev;
57.             prev = curr;
58.             curr = nextTemp;
59.         }
60.         return prev;
61.     }
63.     public static void main(String[] args) {
64.         // 创建测试链表 1 -> 2 -> 2 -> 1
65.         ListNode head = new ListNode(1);
66.         head.next = new ListNode(2);
67.         head.next.next = new ListNode(2);
68.         head.next.next.next = new ListNode(1);
70.         PalindromeLinkedList solution = new PalindromeLinkedList();
71.         // 调用 isPalindrome 方法判断链表是否为回文结构
72.         boolean isPalindrome = solution.isPalindrome(head);
73.         System.out.println(isPalindrome);
74.     }
75. }

复制代码

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

   题目视图：

  题目详解代码：

1. package Demo1_28;
3. /**
4. * Created with IntelliJ IDEA.
5. * Description:
6. * User：Lenovo
7. * Date:2025-01-28
8. * Time:20:08
9. */
10. // 定义链表节点类
11. class ListNode {
12.     int val;
13.     ListNode next;
15.     // 构造函数，用于初始化节点的值
16.     ListNode(int x) {
17.         val = x;
18.         next = null;
19.     }
20. }
22. public class IntersectionOfTwoLinkedLists {
23.     // 查找两个链表相交的起始节点的方法
24.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
25.         // 如果其中一个链表为空，直接返回 null
26.         if (headA == null || headB == null) {
27.             return null;
28.         }
29.         // 初始化两个指针分别指向两个链表的头节点
30.         ListNode pA = headA;
31.         ListNode pB = headB;
32.         // 当两个指针不相等时，继续循环
33.         while (pA != pB) {
34.             // 如果 pA 到达链表 A 的末尾，将其指向链表 B 的头节点
35.             pA = pA == null ? headB : pA.next;
36.             // 如果 pB 到达链表 B 的末尾，将其指向链表 A 的头节点
37.             pB = pB == null ? headA : pB.next;
38.         }
39.         // 返回相交节点，如果不相交则返回 null
40.         return pA;
41.     }
43.     public static void main(String[] args) {
44.         // 创建示例链表
45.         // 链表 A: 1 -> 2 -> 3 -> 6 -> 7
46.         ListNode headA = new ListNode(1);
47.         headA.next = new ListNode(2);
48.         headA.next.next = new ListNode(3);
50.         // 链表 B: 4 -> 5 -> 6 -> 7
51.         ListNode headB = new ListNode(4);
52.         headB.next = new ListNode(5);
54.         // 创建相交部分
55.         ListNode intersection = new ListNode(6);
56.         intersection.next = new ListNode(7);
58.         // 连接链表 A 和相交部分
59.         headA.next.next.next = intersection;
60.         // 连接链表 B 和相交部分
61.         headB.next.next = intersection;
63.         // 创建 IntersectionOfTwoLinkedLists 类的实例
64.         IntersectionOfTwoLinkedLists solution = new IntersectionOfTwoLinkedLists();
65.         // 调用 getIntersectionNode 方法查找相交节点
66.         ListNode result = solution.getIntersectionNode(headA, headB);
67.         if (result != null) {
68.             System.out.println("相交节点的值为: " + result.val);
69.         } else {
70.             System.out.println("两个链表不相交");
71.         }
72.     }
73. }

复制代码

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

   题目视图：

  题目详解代码：

1. // 定义链表节点类
2. class ListNode {
3.     int val;
4.     ListNode next;
6.     // 构造函数，用于初始化节点的值
7.     ListNode(int x) {
8.         val = x;
9.         next = null;
10.     }
11. }
13. public class LinkedListCycle {
14.     // 判断链表是否有环的方法
15.     public boolean hasCycle(ListNode head) {
16.         // 如果链表为空或者只有一个节点，肯定没有环
17.         if (head == null || head.next == null) {
18.             return false;
19.         }
20.         // 慢指针，初始指向头节点，每次移动一步
21.         ListNode slow = head;
22.         // 快指针，初始指向头节点的下一个节点，每次移动两步
23.         ListNode fast = head.next;
24.         // 当慢指针和快指针不相等时，继续循环
25.         while (slow != fast) {
26.             // 如果快指针到达链表末尾或者快指针的下一个节点是末尾，说明没有环
27.             if (fast == null || fast.next == null) {
28.                 return false;
29.             }
30.             // 慢指针移动一步
31.             slow = slow.next;
32.             // 快指针移动两步
33.             fast = fast.next.next;
34.         }
35.         // 如果跳出循环，说明慢指针和快指针相遇了，链表有环
36.         return true;
37.     }
39.     public static void main(String[] args) {
40.         // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）
41.         ListNode node1 = new ListNode(1);
42.         ListNode node2 = new ListNode(2);
43.         ListNode node3 = new ListNode(3);
44.         ListNode node4 = new ListNode(4);
46.         // 构建链表连接关系
47.         node1.next = node2;
48.         node2.next = node3;
49.         node3.next = node4;
50.         // 形成环
51.         node4.next = node2;
53.         // 创建 LinkedListCycle 类的实例
54.         LinkedListCycle solution = new LinkedListCycle();
55.         // 调用 hasCycle 方法判断链表是否有环
56.         boolean result = solution.hasCycle(node1);
57.         System.out.println("链表是否有环: " + result);
59.         // 创建无环链表 1 -> 2 -> 3 -> 4
60.         ListNode nodeA = new ListNode(1);
61.         ListNode nodeB = new ListNode(2);
62.         ListNode nodeC = new ListNode(3);
63.         ListNode nodeD = new ListNode(4);
65.         // 构建无环链表连接关系
66.         nodeA.next = nodeB;
67.         nodeB.next = nodeC;
68.         nodeC.next = nodeD;
70.         // 再次调用 hasCycle 方法判断无环链表是否有环
71.         result = solution.hasCycle(nodeA);
72.         System.out.println("链表是否有环: " + result);
73.     }
74. }

复制代码

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

—题目链接
   题目视图：

  题目详解代码：

1. package Demo1_28;
3. /**
4. * Created with IntelliJ IDEA.
5. * Description:
6. * User：Lenovo
7. * Date:2025-01-28
8. * Time:20:15
9. */
10. // 定义链表节点类
11. class ListNode {
12.     int val;
13.     ListNode next;
14.     ListNode(int x) {
15.         val = x;
16.         next = null;
17.     }
18. }
20. public class LinkedListCycleII {
21.     public ListNode detectCycle(ListNode head) {
22.         // 如果链表为空或只有一个节点，肯定没有环
23.         if (head == null || head.next == null) {
24.             return null;
25.         }
26.         // 慢指针，初始指向头节点，每次移动一步
27.         ListNode slow = head;
28.         // 快指针，初始指向头节点，每次移动两步
29.         ListNode fast = head;
30.         boolean hasCycle = false;
32.         // 寻找是否有环
33.         while (fast != null && fast.next != null) {
34.             slow = slow.next;
35.             fast = fast.next.next;
36.             // 快慢指针相遇，说明有环
37.             if (slow == fast) {
38.                 hasCycle = true;
39.                 break;
40.             }
41.         }
43.         // 如果没有环，返回 null
44.         if (!hasCycle) {
45.             return null;
46.         }
48.         // 慢指针重新指向头节点
49.         slow = head;
50.         // 快慢指针都以每次一步的速度移动，再次相遇的节点就是环的入口节点
51.         while (slow != fast) {
52.             slow = slow.next;
53.             fast = fast.next;
54.         }
55.         return slow;
56.     }
58.     public static void main(String[] args) {
59.         // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）
60.         ListNode node1 = new ListNode(1);
61.         ListNode node2 = new ListNode(2);
62.         ListNode node3 = new ListNode(3);
63.         ListNode node4 = new ListNode(4);
65.         // 构建链表连接关系
66.         node1.next = node2;
67.         node2.next = node3;
68.         node3.next = node4;
69.         // 形成环
70.         node4.next = node2;
72.         // 创建 LinkedListCycleII 类的实例
73.         LinkedListCycleII solution = new LinkedListCycleII();
74.         // 调用 detectCycle 方法找到环的入口节点
75.         ListNode result = solution.detectCycle(node1);
76.         if (result != null) {
77.             System.out.println("环的入口节点的值为: " + result.val);
78.         } else {
79.             System.out.println("链表中没有环");
80.         }
82.         // 创建无环链表 1 -> 2 -> 3 -> 4
83.         ListNode nodeA = new ListNode(1);
84.         ListNode nodeB = new ListNode(2);
85.         ListNode nodeC = new ListNode(3);
86.         ListNode nodeD = new ListNode(4);
88.         // 构建无环链表连接关系
89.         nodeA.next = nodeB;
90.         nodeB.next = nodeC;
91.         nodeC.next = nodeD;
93.         // 再次调用 detectCycle 方法判断无环链表是否有环
94.         result = solution.detectCycle(nodeA);
95.         if (result != null) {
96.             System.out.println("环的入口节点的值为: " + result.val);
97.         } else {
98.             System.out.println("链表中没有环");
99.         }
100.     }
101. }

复制代码

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