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:

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.
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.
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.
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:


# Definition of the Node class for the linked list
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

def find_middle_node(head):
  # First pass: Count the total number of nodes
  count = 0
  current = head
  while current:
    count += 1
    current = current.next
  
  # Calculate the middle position
  middle = count // 2
  
  # Second pass: Traverse to the middle node(s)
  current = head
  for _ in range(middle):
    current = current.next
  
  # For even number of nodes, return both middle nodes
  if count % 2 == 0:
    return current.data, current.next.data
  else:
    return current.data

# Helper function to create a linked list from a list of values
def create_linked_list(values):
  head = Node(values[0])
  current = head
  for value in values[1:]:
    current.next = Node(value)
    current = current.next
  return head

# Example 1: Odd number of nodes (1, 2, 3, 4, 5)
odd_list = create_linked_list([1, 2, 3, 4, 5])
result_odd = find_middle_node(odd_list)
print("Middle node for odd list:", result_odd)

# Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
even_list = create_linked_list([1, 2, 3, 4, 5, 6])
result_even = find_middle_node(even_list)
print("Middle nodes for even list:", result_even)


#include <stdio.h>
#include <stdlib.h>

// Definition of the Node struct for the linked list
struct Node {
  int data;
  struct Node* next;
};

// Function to find the middle node(s) of the linked list
void find_middle_node(struct Node* head, int* result, int* result_count) {
  // First pass: Count the total number of nodes
  int count = 0;
  struct Node* current = head;
  while (current != NULL) {
    count++;
    current = current->next;
  }
  
  // Calculate the middle position
  int middle = count / 2;
  
  // Second pass: Traverse to the middle node(s)
  current = head;
  for (int i = 0; i < middle; i++) {
    current = current->next;
  }
  
  // For even number of nodes, return both middle nodes
  if (count % 2 == 0) {
    result[0] = current->data;
    result[1] = current->next->data;
    *result_count = 2;
  } else {
    result[0] = current->data;
    *result_count = 1;
  }
}

// Helper function to create a linked list from an array of values
struct Node* create_linked_list(int values[], int size) {
  struct Node* head = (struct Node*)malloc(sizeof(struct Node));
  head->data = values[0];
  head->next = NULL;
  
  struct Node* current = head;
  for (int i = 1; i < size; i++) {
    current->next = (struct Node*)malloc(sizeof(struct Node));
    current = current->next;
    current->data = values[i];
    current->next = NULL;
  }
  return head;
}

// Helper function to free the memory allocated for the linked list
void free_linked_list(struct Node* head) {
  struct Node* current = head;
  while (current != NULL) {
    struct Node* temp = current;
    current = current->next;
    free(temp);
  }
}

int main() {
  // Example 1: Odd number of nodes (1, 2, 3, 4, 5)
  int odd_values[] = {1, 2, 3, 4, 5};
  struct Node* odd_list = create_linked_list(odd_values, 5);
  int result_odd[2];
  int result_odd_count;
  find_middle_node(odd_list, result_odd, &result_odd_count);
  
  printf("Middle node for odd list: ");
  for (int i = 0; i < result_odd_count; i++) {
    printf("%d ", result_odd[i]);
  }
  printf("\n");
  
  // Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
  int even_values[] = {1, 2, 3, 4, 5, 6};
  struct Node* even_list = create_linked_list(even_values, 6);
  int result_even[2];
  int result_even_count;
  find_middle_node(even_list, result_even, &result_even_count);
  
  printf("Middle nodes for even list: ");
  for (int i = 0; i < result_even_count; i++) {
    printf("%d ", result_even[i]);
  }
  printf("\n");
  
  // Free the allocated memory
  free_linked_list(odd_list);
  free_linked_list(even_list);
  
  return 0;
}


#include <iostream>
#include <vector>
using namespace std;

// Definition of the Node class for the linked list
class Node {
public:
  int data;
  Node* next;
  
  Node(int val) : data(val), next(nullptr) {}
};

vector<int> find_middle_node(Node* head) {
  // First pass: Count the total number of nodes
  int count = 0;
  Node* current = head;
  while (current) {
    count++;
    current = current->next;
  }
  
  // Calculate the middle position
  int middle = count / 2;
  
  // Second pass: Traverse to the middle node(s)
  current = head;
  for (int i = 0; i < middle; i++) {
    current = current->next;
  }
  
  // For even number of nodes, return both middle nodes
  if (count % 2 == 0) {
    return {current->data, current->next->data};
  } else {
    return {current->data}; // Only one middle node for odd count
  }
}

// Helper function to create a linked list from a vector of values
Node* create_linked_list(const vector<int>& values) {
  if (values.empty()) return nullptr;
  
  Node* head = new Node(values[0]);
  Node* current = head;
  for (size_t i = 1; i < values.size(); i++) {
    current->next = new Node(values[i]);
    current = current->next;
  }
  return head;
}

int main() {
  // Example 1: Odd number of nodes (1, 2, 3, 4, 5)
  Node* odd_list = create_linked_list({1, 2, 3, 4, 5});
  vector<int> result_odd = find_middle_node(odd_list);
  cout << "Middle node for odd list: " << result_odd[0] << endl;

  // Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
  Node* even_list = create_linked_list({1, 2, 3, 4, 5, 6});
  vector<int> result_even = find_middle_node(even_list);
  cout << "Middle nodes for even list: " << result_even[0] << ", " << result_even[1] << endl;

  return 0;
}


// Definition of the Node class for the linked list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

function findMiddleNode(head) {
  // First pass: Count the total number of nodes
  let count = 0;
  let current = head;
  while (current) {
    count++;
    current = current.next;
  }
  
  // Calculate the middle position
  const middle = Math.floor(count / 2);
  
  // Second pass: Traverse to the middle node(s)
  current = head;
  for (let i = 0; i < middle; i++) {
    current = current.next;
  }
  
  // For even number of nodes, return both middle nodes
  if (count % 2 === 0) {
    return [current.data, current.next.data];
  } else {
    return current.data;
  }
}

// Helper function to create a linked list from an array of values
function createLinkedList(values) {
  const head = new Node(values[0]);
  let current = head;
  for (let i = 1; i < values.length; i++) {
    current.next = new Node(values[i]);
    current = current.next;
  }
  return head;
}

// Example 1: Odd number of nodes (1, 2, 3, 4, 5)
const oddList = createLinkedList([1, 2, 3, 4, 5]);
const resultOdd = findMiddleNode(oddList);
console.log("Middle node for odd list:", resultOdd);

// Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
const evenList = createLinkedList([1, 2, 3, 4, 5, 6]);
const resultEven = findMiddleNode(evenList);
console.log("Middle nodes for even list:", resultEven);


import java.util.Arrays;

public class Main {
  // Definition of the Node class for the linked list
  static class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
      this.next = null;
    }
  }

  public static Object findMiddleNode(Node head) {
    // First pass: Count the total number of nodes
    int count = 0;
    Node current = head;
    while (current != null) {
      count++;
      current = current.next;
    }
    
    // Calculate the middle position
    int middle = count / 2;
    
    // Second pass: Traverse to the middle node(s)
    current = head;
    for (int i = 0; i < middle; i++) {
      current = current.next;
    }
    
    // For even number of nodes, return both middle nodes
    if (count % 2 == 0) {
      return new int[]{current.data, current.next.data};
    } else {
      return current.data;
    }
  }

  // Helper function to create a linked list from an array of values
  public static Node createLinkedList(int[] values) {
    Node head = new Node(values[0]);
    Node current = head;
    for (int i = 1; i < values.length; i++) {
      current.next = new Node(values[i]);
      current = current.next;
    }
    return head;
  }

  public static void main(String[] args) {
    // Example 1: Odd number of nodes (1, 2, 3, 4, 5)
    Node oddList = createLinkedList(new int[]{1, 2, 3, 4, 5});
    Object resultOdd = findMiddleNode(oddList);
    System.out.println("Middle node for odd list: " + resultOdd);

    // Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
    Node evenList = createLinkedList(new int[]{1, 2, 3, 4, 5, 6});
    Object resultEven = findMiddleNode(evenList);
    System.out.println("Middle nodes for even list: " + Arrays.toString((int[])resultEven));
  }
}

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.


# Definition of the Node class for the linked list
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

def find_middle_node(head):
  # If the list is empty, return None
  if not head:
    return None
  
  # Initialize slow and fast pointers
  slow = head
  fast = head
  
  # Move slow pointer one step and fast pointer two steps at a time
  while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next
  
  # If the number of nodes is even, return both middle nodes
  if fast.next:
    return slow.data, slow.next.data
  # If the number of nodes is odd, return the middle node
  else:
    return slow.data

# Helper function to create a linked list from a list of values
def create_linked_list(values):
  head = Node(values[0])
  current = head
  for value in values[1:]:
    current.next = Node(value)
    current = current.next
  return head

# Example 1: Odd number of nodes (1, 2, 3, 4, 5)
odd_list = create_linked_list([1, 2, 3, 4, 5])
result_odd = find_middle_node(odd_list)
print("Middle node for odd list:", result_odd)

# Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
even_list = create_linked_list([1, 2, 3, 4, 5, 6])
result_even = find_middle_node(even_list)
print("Middle nodes for even list:", result_even)


#include <stdio.h>
#include <stdlib.h>

// Definition of the Node structure for the linked list
struct Node {
  int data;
  struct Node* next;
};

// Function to find the middle node(s) of the linked list
void find_middle_node(struct Node* head, int* result, int* result_count) {
  // If the list is empty, set result_count to 0
  if (head == NULL) {
    *result_count = 0;
    return;
  }
  
  // Initialize slow and fast pointers
  struct Node* slow = head;
  struct Node* fast = head;
  
  // Move slow pointer one step and fast pointer two steps at a time
  while (fast->next != NULL && fast->next->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
  }
  
  // If the number of nodes is even, return both middle nodes
  if (fast->next != NULL) {
    result[0] = slow->data;
    result[1] = slow->next->data;
    *result_count = 2;
  }
  // If the number of nodes is odd, return the middle node
  else {
    result[0] = slow->data;
    *result_count = 1;
  }
}

// Helper function to create a new node
struct Node* create_node(int data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->data = data;
  new_node->next = NULL;
  return new_node;
}

// Helper function to create a linked list from an array of values
struct Node* create_linked_list(int values[], int size) {
  if (size == 0) return NULL;
  
  struct Node* head = create_node(values[0]);
  struct Node* current = head;
  
  for (int i = 1; i < size; i++) {
    current->next = create_node(values[i]);
    current = current->next;
  }
  
  return head;
}

// Helper function to free the memory allocated for the linked list
void free_linked_list(struct Node* head) {
  struct Node* current = head;
  while (current != NULL) {
    struct Node* temp = current;
    current = current->next;
    free(temp);
  }
}

int main() {
  // Example 1: Odd number of nodes (1, 2, 3, 4, 5)
  int odd_values[] = {1, 2, 3, 4, 5};
  struct Node* odd_list = create_linked_list(odd_values, 5);
  int result_odd[2];
  int result_count_odd;
  
  find_middle_node(odd_list, result_odd, &result_count_odd);
  
  printf("Middle node for odd list: ");
  for (int i = 0; i < result_count_odd; i++) {
    printf("%d ", result_odd[i]);
  }
  printf("\n");
  
  // Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
  int even_values[] = {1, 2, 3, 4, 5, 6};
  struct Node* even_list = create_linked_list(even_values, 6);
  int result_even[2];
  int result_count_even;
  
  find_middle_node(even_list, result_even, &result_count_even);
  
  printf("Middle nodes for even list: ");
  for (int i = 0; i < result_count_even; i++) {
    printf("%d ", result_even[i]);
  }
  printf("\n");
  
  // Free the memory allocated for the linked lists
  free_linked_list(odd_list);
  free_linked_list(even_list);
  
  return 0;
}


#include <iostream>
#include <vector>
using namespace std;

// Definition of the Node class for the linked list
class Node {
public:
  int data;
  Node* next;

  Node(int value) : data(value), next(nullptr) {}
};

// Function to find the middle node(s) of the linked list
vector<int> find_middle_node(Node* head) {
  // If the list is empty, return an empty vector
  if (!head) {
    return {};
  }
  
  // Initialize slow and fast pointers
  Node* slow = head;
  Node* fast = head;
  
  // Move slow pointer one step and fast pointer two steps at a time
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  
  // If the number of nodes is even, return both middle nodes
  if (fast->next) {
    return {slow->data, slow->next->data};
  }
  // If the number of nodes is odd, return the middle node
  else {
    return {slow->data};
  }
}

// Helper function to create a linked list from a vector of values
Node* create_linked_list(const vector<int>& values) {
  if (values.empty()) {
    return nullptr;
  }
  
  Node* head = new Node(values[0]);
  Node* current = head;
  for (size_t i = 1; i < values.size(); ++i) {
    current->next = new Node(values[i]);
    current = current->next;
  }
  return head;
}

// Function to free the memory allocated for the linked list
void free_linked_list(Node* head) {
  Node* current = head;
  while (current) {
    Node* temp = current;
    current = current->next;
    delete temp;
  }
}

int main() {
  // Example 1: Odd number of nodes (1, 2, 3, 4, 5)
  Node* odd_list = create_linked_list({1, 2, 3, 4, 5});
  vector<int> result_odd = find_middle_node(odd_list);
  cout << "Middle node(s) for odd list: ";
  for (size_t i = 0; i < result_odd.size(); ++i) {
    cout << result_odd[i];
    if (i < result_odd.size() - 1) {
      cout << ", ";
    }
  }
  cout << endl;

  // Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
  Node* even_list = create_linked_list({1, 2, 3, 4, 5, 6});
  vector<int> result_even = find_middle_node(even_list);
  cout << "Middle node(s) for even list: ";
  for (size_t i = 0; i < result_even.size(); ++i) {
    cout << result_even[i];
    if (i < result_even.size() - 1) {
      cout << ", ";
    }
  }
  cout << endl;

  // Free the memory allocated for the linked lists
  free_linked_list(odd_list);
  free_linked_list(even_list);

  return 0;
}


// Definition of the Node class for the linked list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

function findMiddleNode(head) {
  // If the list is empty, return null
  if (!head) {
    return null;
  }
  
  // Initialize slow and fast pointers
  let slow = head;
  let fast = head;
  
  // Move slow pointer one step and fast pointer two steps at a time
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  
  // If the number of nodes is even, return both middle nodes
  if (fast.next) {
    return [slow.data, slow.next.data];
  }
  // If the number of nodes is odd, return the middle node
  else {
    return slow.data;
  }
}

// Helper function to create a linked list from an array of values
function createLinkedList(values) {
  const head = new Node(values[0]);
  let current = head;
  for (let i = 1; i < values.length; i++) {
    current.next = new Node(values[i]);
    current = current.next;
  }
  return head;
}

// Example 1: Odd number of nodes (1, 2, 3, 4, 5)
const oddList = createLinkedList([1, 2, 3, 4, 5]);
const resultOdd = findMiddleNode(oddList);
console.log("Middle node for odd list:", resultOdd);

// Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
const evenList = createLinkedList([1, 2, 3, 4, 5, 6]);
const resultEven = findMiddleNode(evenList);
console.log("Middle nodes for even list:", resultEven);


public class Main {
  // Definition of the Node class for the linked list
  static class Node {
    int data;
    Node next;
    
    Node(int data) {
      this.data = data;
      this.next = null;
    }
  }

  public static Object findMiddleNode(Node head) {
    // If the list is empty, return null
    if (head == null) {
      return null;
    }
    
    // Initialize slow and fast pointers
    Node slow = head;
    Node fast = head;
    
    // Move slow pointer one step and fast pointer two steps at a time
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    
    // If the number of nodes is even, return both middle nodes
    if (fast.next != null) {
      return new int[]{slow.data, slow.next.data};
    }
    // If the number of nodes is odd, return the middle node
    else {
      return slow.data;
    }
  }

  // Helper function to create a linked list from an array of values
  public static Node createLinkedList(int[] values) {
    Node head = new Node(values[0]);
    Node current = head;
    for (int i = 1; i < values.length; i++) {
      current.next = new Node(values[i]);
      current = current.next;
    }
    return head;
  }

  public static void main(String[] args) {
    // Example 1: Odd number of nodes (1, 2, 3, 4, 5)
    Node oddList = createLinkedList(new int[]{1, 2, 3, 4, 5});
    Object resultOdd = findMiddleNode(oddList);
    System.out.println("Middle node for odd list: " + resultOdd);

    // Example 2: Even number of nodes (1, 2, 3, 4, 5, 6)
    Node evenList = createLinkedList(new int[]{1, 2, 3, 4, 5, 6});
    Object resultEven = findMiddleNode(evenList);
    System.out.print("Middle nodes for even list: ");
    if (resultEven instanceof int[]) {
      int[] middleNodes = (int[]) resultEven;
      System.out.println(middleNodes[0] + ", " + middleNodes[1]);
    } else {
      System.out.println(resultEven);
    }
  }
}

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).