Linked List Exercise (1) - Middle of the linked list

Leetcode - middle of the linked list (URL)

Entire code

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


class LinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node


    def append(self, value):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        return True


    def find_middle_node(self):
        slow = self.head
        fast = self.head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        return slow


my_linked_list = LinkedList(1)
my_linked_list.append(2)
my_linked_list.append(3)
my_linked_list.append(4)
my_linked_list.append(5)

print( my_linked_list.find_middle_node().value )

"""
    EXPECTED OUTPUT:
    ----------------
    3

"""

Find middle node code

    def find_middle_node(self):
        slow = self.head
        fast = self.head

        while fast is not None and fast.next is not None:
            slow = slow.next # one pointer move
            fast = fast.next.next # two pointer move

        return slow

The find_middle_node method is designed to locate and return the middle node in a linked list. This approach uses two pointers, slow and fast, to traverse the list at different speeds, ultimately allowing slow to stop at the middle node when fast reaches the end.

Step-by-Step Explanation:

1. Initialize Pointers:

   • slow and fast are both initialized to the head of the linked list (self.head).

   • The slow pointer will move one node at a time, while the fast pointer will move two nodes at a time.

2. Loop Condition:

   • The while loop continues as long as both fast is not None and fast.next is not None.

   • This condition ensures that fast can move two nodes ahead without going out of bounds.

3. Pointer Movement:

   • Inside the loop, slow advances one node (slow = slow.next), while fast advances two nodes (fast = fast.next.next).

   • As a result, fast reaches the end of the list in half the time it takes for slow, since it moves at double the speed.

4. Finding the Middle:

   • When fast reaches the end (or one node before the end in an even-length list), slow will be exactly at the middle of the linked list.

   • This is because for every two nodes fast moves, slow only moves one node, effectively dividing the traversal speed by half.

5. Return the Middle Node:

   • Once the loop terminates, slow points to the middle node, which is then returned as the result.

Example:

Suppose the linked list has nodes with values 1 -> 2 -> 3 -> 4 -> 5. Here’s how the pointers move:

• Initial: slow at 1, fast at 1.

• First Loop: slow moves to 2, fast moves to 3.

• Second Loop: slow moves to 3, fast moves to 5.

• The loop ends since fast.next is None.

• The method returns the node where slow is currently located, which has the value 3.

This method works efficiently in O(n) time complexity, where n is the number of nodes, as each pointer only traverses the list once.

Note.

A while loop means that when the condition is True, it repeats again and again. But when it becomes False, the loop stops. In this code, the loop will stop when both fast becomes None and fast.next becomes None.