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

def find_middle(head):
    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)))))
print(find_middle(head).value)

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:

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

print(find_middle(head).value)

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:

def find_middle(head):
    stack = []
    current = head
    # 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

print(find_middle(head).value)

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):
    if not head:
        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

def find_middle(head):
    middle, _, _ = find_middle_helper(head, 0, 0)
    return middle

print(find_middle(head).value)

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:

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

print(find_middle(head).value)

Output: 3

The code creates a Python list from the linked list and directly accesses the middle element. It’s concise and can be written as a one-liner, but it is not memory-efficient as it converts the linked list into a Python list first.

Summary/Discussion

  • Method 1: Two-Pointer Technique. Efficient. Requires only one pass. Best overall performance.
  • Method 2: Count and Traverse. Simple. Requires two passes. Less efficient in comparison to Method 1.
  • Method 3: Using a Stack. Understandable logic. Requires extra memory. Less practical for larger lists.
  • Method 4: Recursive Approach. Elegant. Can cause stack overflow on very long lists. Not the most memory-efficient.
  • Method 5: List Comprehension. Concise one-liner. Not memory-efficient as it requires the creation of a list from the linked list.