876-middle-of-the-linked-list

876. Середина связного списка (Easy) (https://leetcode.com/problems/middle-of-the-linked-list/)

Дана голова односвязного списка, нужно вернуть средний узел связного списка. Если есть два средних узла, вернуть второй из них.

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}
 
function middleNode(head: ListNode | null): ListNode | null {
  // Floyd's slow/fast pointers
  let slow = head
  let fast = head
 
  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
  }
 
  return slow
}
 
// Local check:
function toList(arr: number[]): ListNode | null {
  if (arr.length === 0) return null
  const head = new ListNode(arr[0])
  let cur = head
  for (let i = 1; i < arr.length; i++) {
    cur.next = new ListNode(arr[i])
    cur = cur.next
  }
  return head
}
 
function toArray(node: ListNode | null): number[] {
  const out: number[] = []
  while (node !== null) {
    out.push(node.val)
    node = node.next
  }
  return out
}
 
console.log(toArray(middleNode(toList([1, 2, 3, 4, 5]))))
console.log(toArray(middleNode(toList([1, 2, 3, 4, 5, 6]))))

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.

linked-list 141 — тот же fast & slow pointer patterns leetcode