876. 链表的中间结点
876. 链表的中间结点
题目
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 | 链表最大孪生和 | 栈 链表 双指针 |