Problem

Given a singly linked list, return the middle node of the list. If the list has an even number of nodes, return the node at the end of the first half of the list.
Example input: 1 -> 2 -> 3 -> 4 -> 5
Example output: 3

Solution

# The optimal solution is to use two pointers, one that moves one node at a time and another that moves two nodes at a time.
# When the second pointer reaches the end of the list, the first pointer will be at the middle of the list.
# This solution is optimal because it only requires one pass through the list.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

    def middle _node(self):
        slow_pointer = self.head
        fast_pointer = self.head
        while fast_pointer and fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next
        return slow_pointer.data

llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
llist.append(5)
llist.append(6)

print(llist.middle_node())