当前位置：首页 > news >正文

LeetCode 解题思路 15（Hot 100）

news 2025/3/14 11:01:06

在这里插入图片描述

解题思路：

引入哑节点： 简化头节点删除操作，统一处理所有边界条件。
快慢指针法： 快指针先移动 n 步，确保快慢指针距离为 n，之后同步移动快慢指针。当快指针到达末尾时，慢指针指向倒数第 n 个节点的前驱。
删除节点： 调整慢指针的 next 指针，跳过目标节点。

Java代码：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode fast = dummy, slow = dummy;for (int i = 0; i < n; i++) fast = fast.next;while (fast.next != null) {slow = slow.next;fast = fast.next;}slow.next = slow.next.next;return dummy.next;}
}

复杂度分析：

时间复杂度： O(m)，其中m是链表的长度。
空间复杂度： O(1)，只使用了常数级别的额外空间。

在这里插入图片描述

解题思路：

创建哑节点： 作为新链表的头前驱，统一处理头节点交换。
初始化指针： prevEnd：标记当前交换对的末尾，初始指向哑节点。first 和 second：指向待交换的两个节点。
交换节点： 保存 second 的下一个节点 nextNode。调整指针顺序：prevEnd → second → first → nextNode。
移动指针： prevEnd 移动到当前交换后的第一个节点（原 first），继续处理下一对。
终止条件： 当剩余节点不足两个时停止循环。

Java代码：

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head;ListNode dummy = new ListNode(-1);dummy.next = head;ListNode prevEnd = dummy;ListNode first = prevEnd.next;ListNode second = first.next;while (first != null && second != null) {ListNode nextNode = second.next;prevEnd.next = second;second.next = first;first.next = nextNode;prevEnd = first;first = prevEnd.next;if (first == null) break;second = first.next;if (second == null) break;}return dummy.next;}
}