Finding the Middle Node(s) in a Linked List Data Structure

Finding the middle node(s) in a linked list involves identifying the element(s) present at the center of a linked list data structure. This operation is crucial in various applications, such as efficiently splitting a linked list into two halves, optimizing certain algorithms that require balanced partitioning of data etc.

Prerequisite for this article: Basics of Linked List Data Structure, Traversing a Linked List Data Structure.

Problem Statement

The problem of finding the middle node(s) in a linked list can be defined as follows:

• Given a linked list, identify and return the node(s) that occupy the middle position(s) of the list.
• For a list with n nodes (using zero-based positioning):
  • If n is odd, the middle node is at position ⌊n/2⌋ (where ⌊ ⌋ denotes the floor function).
  • If n is even, there are two middle nodes at position (n/2) - 1 and (n/2).
• For a list with 3 nodes (odd), the middle node is at index ⌊3/2⌋ = 1.
• For a list with 4 nodes (even), the middle nodes are at indices (4/2) - 1 = 1 and (4/2) = 2.

Examples

Let’s look at a few examples to better understand the problem:

1. Odd-length list: 1 -> 2 -> 3 -> 4 -> 5

   • Input: Head of the list (node with value 1)
   • Output: Node with value 3
   • Reasoning: In a list with 5 nodes, the middle node is at position ⌊5/2⌋ = 2 (0-based index), which is the node with value 3.

2. Even-length list: 1 -> 2 -> 3 -> 4 -> 5 -> 6

   • Input: Head of the list (node with value 1)
   • Output: Node with value 3 or nodes with values 3 and 4 (depending on the problem variation)
   • Reasoning: In a list with 6 nodes, the middle nodes are at positions (6/2) - 1 = 2 and (6/2) = 3 (0-based index), which are the nodes with values 3 and 4.

3. Single-node list: 42

   • Input: Head of the list (node with value 42)
   • Output: Node with value 42
   • Reasoning: In a list with only one node, that node is considered the middle node.

4. Empty list: null

   • Input: null (empty list)
   • Output: null
   • Reasoning: An empty list has no middle node, so we return null.

Constraints and Assumptions

• The problem is typically presented for singly linked lists, where each node only has a reference to the next node.
• For doubly linked lists, the solution approach might differ slightly due to the availability of backward links.
• The list is assumed to be non-circular without any loops unless explicitly stated otherwise.
• The length of the list is not known beforehand.
• The list may contain duplicate values, but this doesn’t affect the problem of finding the middle node(s).

Approaches to Find the Middle Node(s)

There are several approaches to find the middle node(s) in a linked list. Let’s explore three common methods: the brute force approach, the two-pointer approach (optimal solution), and approaches using extra space.

Brute Force Approach

The brute force approach is a straightforward method that involves two passes through the linked list:

• First pass: Count the total number of nodes in the list.
• Second pass: Traverse the list again to reach the middle node(s).

Below is the implementation in various programming languages:

Time Complexity: O(n), where n is the number of nodes in the list. We traverse the list twice, but this is still linear time.

Space Complexity: O(1), as we only use a constant amount of extra space regardless of the input size.

Two-Pointer Approach (Optimal Solution)

The two-pointer approach is an elegant and efficient solution which allows us to find the middle element in a linked list using just a single loop. Below is the algorithm:

• Use two pointers: a slow pointer and a fast pointer.
• Move the slow pointer one step at a time and the fast pointer two steps at a time.
• When the fast pointer reaches the end (or second-to-last node for even-length lists), the slow pointer will be at the middle.

This method works for both odd and even length lists:

• For odd-length lists: When the fast pointer reaches the last node, the slow pointer is at the middle.
• For even-length lists: When the fast pointer reaches null (after the last node), the slow pointer is at the first of the two middle nodes.

Time Complexity: O(n), where n is the number of nodes. We traverse the list only once.

Space Complexity: O(1), as we only use two pointers regardless of the list size.

Using Extra Space

Below are some other approaches to find the middle element in a linked list using additional data structures:

• Array-based approach:

  • Store all node references in an array while traversing the list.
  • Access the middle element(s) of the array.

• Stack-based approach:

  • Push all nodes onto a stack while traversing the list.
  • Pop half the elements to find the middle node(s).

Pros:

• Easy to implement and understand.
• Allows quick access to any node in the list once stored.

Cons:

• Higher space complexity compared to the other approaches.
• Requires additional time to populate the extra data structure.

Time Complexity: O(n) for both approaches.

Space Complexity: O(n), as we store references to all nodes in the extra data structure.

While these methods work, they are generally less efficient than the two-pointer approach in terms of space usage and are not typically preferred for this specific problem.

Variations and Extensions

• Cycle Detection: Find if there are cycles or loops in a linked list and find the node where the cycle starts.
• Fractional Node Location: Locate nodes at specific fractions of the list length using a modified two-pointer approach. Adjust fast pointer speed to move 3x or 4x faster than slow pointer and modify ending condition based on desired fraction (1/3 or 1/4).