# 5 Best Ways to Find the Middle Node of a Singly Linked List in Python

Rate this post

π‘ Problem Formulation: Given a singly linked list, the challenge is to find the middle node — the node that is equidistant from both the start and the end, when you have an odd number of nodes, or one of the two middle nodes when there are an even number of nodes. For instance, if the input linked list is 1 -> 2 -> 3 -> 4 -> 5, the desired output is the node containing the value 3.

## Method 1: Two-Pointer Technique

The two-pointer technique involves using two pointers that traverse the linked list at different speeds, a slow pointer, and a fast pointer. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. Once the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Here’s an example:

class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next

slow_ptr = fast_ptr = head
while fast_ptr and fast_ptr.next:
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next.next
return slow_ptr

# Example linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))

Output: 3

The provided code defines a linked list and a function to find its middle. It successfully identifies node 3 as the middle when there are 5 total nodes using the two-pointer technique, which is efficient and only requires a single pass through the list.

## Method 2: Count and Traverse

In the count and traverse method, we first traverse the entire list to count the number of nodes. Then, we traverse the list again but only to half of the counted length, positioning us at the middle node.

Here’s an example:

counter = 0
# Count the total number of nodes
while current:
counter += 1
current = current.next
# Find the middle index
middle_index = counter // 2
# Traverse to the middle index
for _ in range(middle_index):
current = current.next
return current

Output: 3

This code counts the total nodes using one full pass, then finds the middle node index. In the second pass, it moves to the middle node. It’s simple but requires two passes over the list, making it less efficient than the two-pointer technique.

## Method 3: Using a Stack

Using a stack, we can push all nodes onto the stack and then pop half of them to get to the middle. As stacks use the Last-In-First-Out (LIFO) approach, once half of the nodes are popped off, the top of the stack will be the middle node.

Here’s an example:

stack = []
# Push all nodes onto the stack
while current:
stack.append(current)
current = current.next
# Pop half of the nodes
for _ in range(len(stack) // 2):
middle = stack.pop()
return middle

Output: 3

The code uses a stack to identify the middle node. After pushing all nodes to the stack, it pops half of the nodes. The top of the stack will then be the middle node. This approach, while simple to understand, requires extra memory proportional to the size of the list.

## Method 4: Recursive Approach

The recursive approach involves a helper function that utilizes recursion to track the index of the current node and the length of the linked list simultaneously. When it reaches the end of the list, it uses the calculated length to identify the middle node.

Here’s an example:

def find_middle_helper(head, index, length):
return None, index, length
if index == length // 2:
return head, index, length
middle, index, length = find_middle_helper(head.next, index + 1, length + 1)
return middle, index, length

middle, _, _ = find_middle_helper(head, 0, 0)
return middle

Output: 3

This recursive function traverses the linked list, incrementing the index and length with each recursive call. It uses these values to return the middle node. While elegant, the recursive approach is not the most memory-efficient due to its call stack and may not be suitable for very long lists.

## Bonus One-Liner Method 5: List Comprehension

If Python lists are allowed for a one-off conversion, a one-liner solution involves converting the linked list into a Python list with list comprehension and then accessing the middle element directly.

Here’s an example:

lst = [node for node in iter(head)]
return lst[len(lst) // 2]