Java链表算法精练
链表元素删除
目标：移除链表中所有数值等于特定值的节点
实现策略：
采用双指针遍历法，当快指针定位到目标节点时，调整慢指针的next指向跳过该节点；若未发现目标值，双指针同步后移保持固定间距
具体步骤：
1.初始化指针：pre指向头节点，cur指向后继节点
2.遍历检测：
发现目标节点时
pre.next = cur.next;
cur = cur.next;
未发现目标节点时
pre = cur;
cur = cur.next;
3.特别处理头节点：
最后单独检查首节点是否需删除
若需删除则执行 head = head.next;
定位删除流程
发现目标节点后修改前驱节点指向
持续遍历检测
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) return null;
ListNode pre = head;
ListNode cur = head.next;
while(cur != null) {
if(cur.val == val) {
pre.next = cur.next;
cur = cur.next;
} else {
pre = cur;
cur = cur.next;
}
}
if(head.val == val) {
head = head.next;
}
return head;
}
}
注意：将头节点检查置于最后可避免多次修改头指针，简化操作流程
单链表逆序操作
目标：实现链表节点的完全逆序排列
核心思想：通过迭代方式将后续节点逐个前移，最终使原尾节点成为新头节点
实现要点：
1.使用cur指针遍历链表
2.每次操作前保存后继节点地址，防止链表断裂
3.逐步修改节点指向关系
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode cur = head.next;
head.next = null;
while(cur != null) {
ListNode temp = cur.next;
cur.next = head;
head = cur;
cur = temp;
}
return head;
}
}
定位链表中点
目标：准确找到链表的中间位置，当节点数为偶数时返回第二个中间节点
解决方案：快慢指针法，快指针步长为慢指针两倍
数学原理：相同时间内，快指针移动距离是慢指针的两倍，故快指针抵达终点时，慢指针正好处于中点位置
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null) return null;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
获取链表倒数节点
目标：高效定位倒数第K个节点（假设K值有效）
实现方案：固定间距的双指针法
操作步骤：
1.快指针先行K-1步
2.双指针同步移动直至快指针到达末尾
3.此时慢指针即为所求
class Solution {
public int kthToLast(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i=0; i<k-1; i++) {
fast = fast.next;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow.val;
}
}
有序链表合并
目标：将两个有序链表合并为新的有序链表
实现策略：比较节点值大小，按序连接
关键步骤：
1.创建哨兵节点简化操作
2.循环比较选取较小节点
3.处理剩余节点
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
回文链表检测
目标：判断链表是否为回文结构
解决方案：后半部分逆序+双端比较法
实施步骤：
1.定位中点（快慢指针）
2.逆序后半部分
3.头尾双指针比较
public class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
// 定位中点
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 逆序后半部分
ListNode prev = null;
while(slow != null) {
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// 双端比较
ListNode start = head;
ListNode end = prev;
while(end != null) {
if(start.val != end.val) {
return false;
}
start = start.next;
end = end.next;
}
return true;
}
}
