Skip to main content

876. Middle of the Linked List

分析

双指针技巧

这题的有趣之处在于对于中点的定位

奇数情况
1 -> 2 -> 3 -> 4 -> 5
3

偶数情况
1 -> 2 -> 3 -> 4
3

其实偶数的情况可以是3 可以是2,题目这里要求为3

如果想保持这个获取2和3的灵活,觉得加一个dummyNode 来处理是更合适的

dummyNode -> 1 -> 2 -> 3 -> 4 -> 5

将 -> 1 看做是 基本的单位

关于 灵活性的场景 参考下 148. Sort List 对这里的使用 关于基本单位的思考 可以结合 160. Intersection of Two Linked Lists

Pasted image 20220521110427.png 觉得从 head 开始更简洁一些

  • 需要重新整理下

题解

// [1,2,3,4,5,6]
// 1 2, 2 4, 3 6
// [1,2,3,4,5]
// 1 2, 2 4, 3 null
function middleNode(head: ListNode | null): ListNode | null {
const dummyNode = new ListNode()
dummyNode.next = head
let slow = dummyNode, fast = dummyNode
while (fast?.next) {
fast = fast.next.next
slow = slow.next
}
return fast ? slow.next : slow
};
function middleNode(head: ListNode | null): ListNode | null {
let fast = head, slow = head
while (fast?.next?.next) {
fast = fast.next.next
slow = slow.next
}

return fast.next ? slow.next : slow
};