Find middle node of a singly linked list

Given a pointer to the head of a singly linked list find the middle node of the linked list.

Middle Nodes in Odd and
Even length linked lists

Method 1: Using two traversals

1. Traverse the linked list and count the number of nodes present in the linked list.

2. start a loop from 0 to count/2 and do current = current.next

3. return the current pointer

The logic is fairly simple, we count the total number of nodes in the list and then traverse the list second time for half the size of the list.

Method 2: Using race pointer method

This problem can be solved in a single traversal using the method I call race pointer method.

Imagine two runners, A and B, on a race track.

If Runner A runs twice as fast as Runner B, then, when Runner A will be on the finish line, Runner B would be in the middle of the race track.

The same concept can be used to find the middle node by using two pointers, fast and slow. The fast pointer will be updated twice in the loop:

fast = fast.next

fast = fast.next

while slow pointer will be updated just once:

slow = slow.next

Once the fast pointer becomes None or Null, our slow pointer will be at the required position and we could simply return the slow pointer.

Code in Python:

# Python program to find middle node of a singly linked list


# Node class
class Node:

    # Constructor to initialise data and next
    def __init__(self, data=None):
        self.data = data
        self.next = None


class SinglyLinkedList:

    # Constructor to initialise head
    def __init__(self):
        self.head = None

    # Function to find middle node of a linked list
    def find_mid(self):
        fast = self.head
        slow = self.head

        # Make fast run twice the speed of slow
        # when fast is at the last of the list
        # slow will be at the mid node
        while fast is not None:

            # updated fast once
            fast = fast.next

            if fast is not None:

                # update fast twice
                fast = fast.next
                slow = slow.next

        return slow

    # Function to Insert data at the beginning of the linked list
    def insert_at_beg(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # Function to print the linked list
    def print_data(self):
        current = self.head
        while current is not None:
            print(current.data, '-> ', end='')
            current = current.next
        print('None')

# Main code:
linked_list = SinglyLinkedList()
linked_list.insert_at_beg(9)
linked_list.insert_at_beg(8)
linked_list.insert_at_beg(7)
linked_list.insert_at_beg(6)
linked_list.insert_at_beg(5)
linked_list.insert_at_beg(4)
linked_list.insert_at_beg(3)
linked_list.insert_at_beg(2)
linked_list.insert_at_beg(1)
linked_list.print_data()
# call the find_mid function
mid = linked_list.find_mid()
# print the middle node if not None
if mid is not None:
    print(mid.data)

"""
Outputs:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> None
5
"""

Time & Space Complexity:

The algorithm runs in O(n) time complexity where n is the number of nodes.

It takes O(1) space as we only use 2 pointers fast and slow, which is independent of the linked list size.

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal