Java数据结构精讲：深入探索链表操作与面试题解析（第三部分）

专题系列：Java数据结构解析

作者主页：编程探索者
内容导航
一、链表常见面试题精解
1.1. 链表元素分割问题
1.2. 判断回文链表
1.3. 寻找链表交点
1.4. 检测环形链表

一、链表常见面试题精解

1.1. 链表元素分割问题

题目要求保持原始数据顺序不变。我们可以通过遍历链表，将节点根据给定值x分成前后两部分。具体实现时，需要维护四个指针分别表示两个子链表的首尾节点。在插入操作时，需要注意更新尾指针的位置，确保始终指向当前链表的最后一个节点。最后将两个子链表连接时，要特别处理边界情况，避免形成循环引用。

class ListNode{
int value;
ListNode nextNode;
ListNode(int value){
this.value = value;
}
}
public class ListPartitioner {
public ListNode partitionList(ListNode head, int threshold){
ListNode beforeStart = null;
ListNode beforeEnd = null;
ListNode afterStart = null;
ListNode afterEnd = null;
ListNode current = head;
while(current != null){
if(current.value
特别注意：当处理完成后，必须显式地将最后一个节点的next置为null，否则可能导致链表循环。
完整实现：
```java
class ListNode{
int value;
ListNode nextNode;
ListNode(int value){
this.value = value;
}
}
public class ListPartitioner {
public ListNode partitionList(ListNode head, int threshold){
ListNode beforeStart = null;
ListNode beforeEnd = null;
ListNode afterStart = null;
ListNode afterEnd = null;
ListNode current = head;
while(current != null){
if(current.value  "判断回文链表")
解法一：可以考虑使用双指针技术，但由于单链表的单向性，这种方法实现较为复杂。
解法二：将链表值存入数组进行判断，但这样会增加空间复杂度。
最优解：采用链表反转结合中点查找的方法。具体步骤包括：
1. 定位链表中间节点
2. 反转后半部分链表
3. 比较前后两部分节点值
<img src="https://pic1.imgdb.cn/item/6824af8558cb8da5c8f1bfe7.png" alt="">
链表反转核心代码：
```java
while(current != null){
ListNode nextNode = current.nextNode;
current.nextNode = prev;
prev = current;
current = nextNode;
}

对于偶数长度链表的特殊情况，需要额外判断相邻节点的情况。
完整解决方案：

class ListNode{
int value;
ListNode nextNode;
ListNode(int value){
this.value = value;
}
}
public class PalindromeChecker {
public boolean isPalindrome(ListNode head){
// 定位中点
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.nextNode != null){
fast = fast.nextNode.nextNode;
slow = slow.nextNode;
}
// 反转后半部分
ListNode prev = null;
ListNode current = slow;
while(current != null){
ListNode next = current.nextNode;
current.nextNode = prev;
prev = current;
current = next;
}
// 比较前后部分
while(head != prev){
if(head.value != prev.value){
return false;
}
// 处理偶数长度情况
if(head.nextNode == prev){
return true;
}
head = head.nextNode;
prev = prev.nextNode;
}
return true;
}
}

1.3. 寻找链表交点

首先需要明确链表相交的形式是Y型而非X型。解题思路如下：
1. 计算两个链表的长度差
2. 让较长链表的指针先移动差值步数
3. 同步移动两个指针直到相遇


实现时需要注意处理链表长度计算和指针移动的边界条件。

1.4. 检测环形链表

采用快慢指针技术：慢指针每次移动一步，快指针每次移动两步。如果存在环，两指针必定会相遇；否则快指针会先到达链表末尾。


为什么选择2倍速？考虑最坏情况，当快指针刚完成一圈时，慢指针刚进入环，此时每次移动都会缩小两者距离，最终必然相遇。
实现代码：

class ListNode{
int value;
ListNode nextNode;
ListNode(int value){
this.value = value;
}
}
public class CycleDetector {
public boolean hasCycle(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.nextNode != null){
slow = slow.nextNode;
fast = fast.nextNode.nextNode;
if(slow == fast){
return true;
}
}
return false;
}
}