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

飞不高 · 2025-2-13 17:21:53

我的个人主页
我的专栏：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("链表中没有环");
}
}
}

复制代码

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

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云