2095. 删除链表的中间节点

🟠   🔖  链表 双指针  🔗 力扣 LeetCode

题目

You are given the head of a linked list. Delete the middle node , and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing , where ⌊x⌋ denotes the largest integer less than or equal to x.

• For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]

Output: [1,3,4,1,2,6]

Explanation:

The above figure represents the given linked list. The indices of the nodes are written below.

Since n = 7, node 3 with value 7 is the middle node, which is marked in red.

We return the new list after removing this node.

Example 2:

Input: head = [1,2,3,4]

Output: [1,2,4]

Explanation:

The above figure represents the given linked list.

For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]

Output: [2]

Explanation:

The above figure represents the given linked list.

For n = 2, node 1 with value 1 is the middle node, which is marked in red.

Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 1 <= Node.val <= 10^5

题目大意

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

• 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入： head = [1,3,4,7,1,2,6]

输出：[1,3,4,1,2,6]

解释：

上图表示给出的链表。节点的下标分别标注在每个节点的下方。

由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。

返回结果为移除节点后的新链表。

示例 2：

输入： head = [1,2,3,4]

输出：[1,2,4]

解释：

上图表示给出的链表。

对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

示例 3：

输入： head = [2,1]

输出：[2]

解释：

上图表示给出的链表。

对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。

值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

提示：

• 链表中节点的数目在范围 [1, 105] 内
• 1 <= Node.val <= 10^5

解题思路

中间节点的定义：

• 如果链表的长度是奇数，中间节点是唯一的。
• 如果链表的长度是偶数，中间节点是中间偏右的那个节点（第二个节点）。

1. 初始化：

   • slow 和 fast 都初始化为链表的头节点。
   • prev 用于保存慢指针前一个节点的位置。

2. 使用快慢指针：

   • 在 while 循环中，快指针每次走两步，慢指针每次走一步。
   • 当快指针达到链表末尾时，慢指针恰好指向链表的中间节点。

3. 删除操作：当找到中间节点时，慢指针的前一个节点 prev 会指向慢指针的下一个节点，实际上就删除了中间节点。

4. 返回链表的头节点 head，此时链表已经删除了中间节点。

时间复杂度

• 时间复杂度： O(n)，其中 n 是链表的长度，快慢指针遍历链表一次。
• 空间复杂度： O(1)，只使用了常数空间来存储指针（快指针、慢指针、前一个节点）。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteMiddle = function (head) {
	// 如果链表只有一个节点，删除后链表为空
	if (!head || !head.next) {
		return null;
	}

	let slow = head,
		fast = head,
		prev = null;

	// 使用快慢指针找到中间节点的前一个节点
	while (fast && fast.next) {
		prev = slow; // 慢指针前一个节点
		fast = fast.next.next; // 快指针走两步
		slow = slow.next; // 慢指针走一步
	}

	// 删除慢指针指向的中间节点
	prev.next = slow.next;

	return head;
};

相关题目

题号	标题	题解	标签	难度	力扣
19	删除链表的倒数第 N 个结点	[✓]	链表 双指针	🟠	🀄️ 🔗
143	重排链表	[✓]	栈 递归 链表 1+	🟠	🀄️ 🔗
203	移除链表元素	[✓]	递归 链表	🟢	🀄️ 🔗
876	链表的中间结点	[✓]	链表 双指针	🟢	🀄️ 🔗