Coding Interview Questions | Middle of Linked List

January 3rd, 2024

Maximum Depth Problem Introduction:

This summary will talk about my solution to the middle of the linked list problem as seen on leetcode here.

How do you solve the Middle of the Linked List Problem in O(n) time?

Solution:

function middleNode(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = slow;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  return slow;
}

Middle Node Solution Summary:

Below is an analysis of the key components of the provided solution:

1. Two-Pointer Approach: The algorithm employs a two-pointer approach with slow and fast pointers. Initially, both pointers are set to the head of the linked list.

2. Traversal Criteria: The while loop continues as long as the fast pointer and its next node (fast.next) are not null. This ensures that the traversal proceeds until the end of the linked list.

3. Pointer Movement: In each iteration, the slow pointer moves one step (slow = slow!.next), while the fast pointer advances two steps (fast = fast.next.next). This results in the slow pointer reaching the middle when the fast pointer reaches the end.

4. Return Middle Node: The algorithm returns the node pointed to by the slow pointer, which corresponds to the middle node of the linked list.

Complexities

1. Time Complexity: The time complexity of the solution is O(n), where n is the number of nodes in the linked list. The two-pointer approach allows traversing the list in a single pass.

2. Space Complexity: The space complexity is O(1) as the algorithm uses a constant amount of extra space, regardless of the input size.