Frontend School

Find the Middle Node of a Linked List

DSA
easy

Find the Middle Node of a Linked List

Easy
Linked List
Two Pointers

Overview

In Uber's backend systems, linked lists might be used to represent sequences of events, trip segments, or even driver queues. Sometimes, it's necessary to quickly identify a central point in such a sequence, perhaps to split a task, balance load, or find a representative element. This problem focuses on efficiently locating the middle element of a given sequence represented as a singly linked list.

What you need to do / Task

Implement a function middleNode that takes the head of a singly linked list and returns its middle node. If the list has an even number of nodes, return the second middle node.

Input & output

  • Input: head - The head node of a singly linked list. Each node has an integer val and a next pointer.
  • Output: Return the middle node of the list. If there are two middle nodes (even length list), return the second one.

Clarifications

  • Empty list: The input head will always point to a valid ListNode or be null. However, for this problem, assume the list will always contain at least one node.
  • Second middle node: For a list like [1, 2, 3, 4, 5, 6], the middle nodes are 3 and 4. You should return the node with value 4.

Examples

1

Example 1

Input:

head = [1,2,3,4,5]

Output:

[3,4,5]

Note:

The list has 5 nodes. The middle node is the 3rd node, with value 3.

2

Example 2

Input:

head = [1,2,3,4,5,6]

Output:

[4,5,6]

Note:

The list has 6 nodes. The two middle nodes are 3 and 4. We return the second middle node, which has value 4.

3

Example 3

Input:

head = [1]

Output:

[1]

Note:

The list has 1 node. The middle node is the 1st node, with value 1.

Constraints

Constraints & assumptions

  • The number of nodes in the list is between 1 and 100.
  • 1 <= Node.val <= 1000.
  • The linked list is singly-linked.

Out of scope

  • You do not need to handle circular linked lists or doubly-linked lists.
  • You do not need to modify the structure of the linked list; just return a reference to the middle node.

What interviewers evaluate

  • Correctness in identifying the middle node for both odd and even length lists.
  • Efficiency of the chosen algorithm in terms of time and space complexity.
  • Clarity, readability, and maintainability of the code.
  • Ability to handle edge cases, such as a list with a single node.

Loading editor...