💡 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.
♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month
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.