876. Middle of the Linked List

🟢   🔖  链表 双指针  🔗 LeetCode

题目

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

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

Output: [3,4,5]

Explanation: The middle node of the list is node 3.

Example 2:

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

Output: [4,5,6]

Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

题目大意

输出链表中间结点。这题在前面题目中反复出现了很多次了。

如果链表长度是奇数，输出中间结点是中间结点。如果链表长度是双数，输出中间结点是中位数后面的那个结点。

解题思路

• 思路一：单指针

  • 先遍历一遍链表，统计一下节点个数为 n，再遍历到 n / 2 的位置，返回中间节点；
  • 需要注意的一个特例是，有可能要删除头节点，在遍历之前，新建一个头节点，让其指向原来的头节点。

• 思路二：快慢指针

  • 使用步长不一致的快慢指针进行一次遍历找到链表的中间节点；
  • 使用两个指针 slow、fast，都指向链表的头节点;
  • 将快、慢指针同时向右移动，其中慢指针每次移动 1 步，即 slow = slow.next；快指针每次移动 2 步，即 fast = fast.next.next；
  • 等到快指针移动到链表尾部（即 fast.next == null）时跳出循环体，此时 slow 指向链表中间位置；
  • 返回 slow 指针。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
	let slow = head;
	let fast = head;
	while (fast && fast.next) {
		slow = slow.next;
		fast = fast.next.next;
	}
	return slow;
};

相关题目

相关题目

• 2095. 删除链表的中间节点
• 2130. 链表最大孪生和

- [2095. 删除链表的中间节点](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list)
- [2130. 链表最大孪生和](https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list)