跳至主要內容

876. 链表的中间结点


876. 链表的中间结点open in new window

🟢   🔖  链表 双指针  🔗 力扣open in new window LeetCodeopen in new window

题目

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 的位置,返回中间节点;
    • 需要注意的一个特例是,有可能要删除头节点,在遍历之前,新建一个头节点,让其指向原来的头节点。
  • 思路二:快慢指针

    • 使用步长不一致的快慢指针进行一次遍历找到链表的中间节点;
    • 使用两个指针 slowfast,都指向链表的头节点;
    • 将快、慢指针同时向右移动,其中慢指针每次移动 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删除链表的中间节点open in new window链表 双指针
2130链表最大孪生和open in new window 链表 双指针