链表的中间结点（876）

题目

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例

输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5])

输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6])

提示

给定链表的结点数介于 1 和 100 之间。

算法

两次遍历

第一次遍历链表，统计链表长度

第二次找到中间结点并返回

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const middleNode = (head) => {
	let count = 0;
	let node = head;
	while (node) {
		count++;
		node = node.next;
	}
	count = count % 2 === 1 ? (count - 1) / 2 : count / 2;
	while (count-- > 0) {
		head = head.next;
	}
	return head;
};

快慢指针

两个指向head的指针，快指针走两步，慢指针走一步。快指针走到终点时，慢指针恰好是一半的位置

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const middleNode = (head) => {
	let fast = head,
		slow = head;
	while (fast !== null && fast.next !== null) {
		slow = slow.next;
		fast = fast.next.next;
	}
	return slow;
};