Easy

Middle of the Linked List

023

Given a linked list encoded as an array, return the values from the middle node to the end.

EXAMPLES

Example 1

Input
{
  "head": [
    1,
    2,
    3,
    4,
    5
  ]
}

Output
[
  3,
  4,
  5
]

FUNCTION SHAPE

head: intArray→intArray

SOLUTION NOTE

When fast pointer moves at twice the speed of slow, by the time fast reaches the end, slow will be at the middle. For even-length lists, this gives us the second of the two middle nodes, as required.

Reveal reference solution +

pythonREFERENCE

def middleNode(self, head: ListNode) -> ListNode:
    # Iterative solution using fast and slow pointers
    # Initialize slow and fast pointers
    slow = head
    fast = head

    # Move slow one step and fast two steps at a time
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # When fast reaches the end, slow is at the middle
    return slow

# Recursive solution using a two-pass approach
def middleNodeRecursive(self, head: ListNode) -> ListNode:
    # First pass: count the number of nodes
    def count_nodes(node):
        if not node:
            return 0
        return 1 + count_nodes(node.next)

    # Second pass: find the middle node
    def find_middle(node, current, target):
        if current == target:
            return node
        return find_middle(node.next, current + 1, target)

    # Count the nodes and calculate the middle position
    length = count_nodes(head)
    middle_pos = length // 2  # Integer division gives the second middle for even lengths

    # Find the middle node
    return find_middle(head, 0, middle_pos)

TimeO(n)

SpaceO(1) iterative, O(n) recursive

Open on LeetCode ↗