|
| 1 | +# Node class represents each element in the linked list |
| 2 | +class Node: |
| 3 | + def __init__(self, data): |
| 4 | + self.data = data # The value stored in the node |
| 5 | + self.next = None # Pointer to the next node in the list |
| 6 | + |
| 7 | +# LinkedList class contains the head of the list and methods to manipulate it |
| 8 | +class LinkedList: |
| 9 | + def __init__(self): |
| 10 | + self.head = None # The starting point of the list |
| 11 | + |
| 12 | + # Method to add a new node to the end of the list |
| 13 | + def append(self, data): |
| 14 | + new_node = Node(data) |
| 15 | + # If the list is empty, the new node becomes the head |
| 16 | + if not self.head: |
| 17 | + self.head = new_node |
| 18 | + return |
| 19 | + # Otherwise, traverse to the end of the list and add the new node |
| 20 | + last_node = self.head |
| 21 | + while last_node.next: |
| 22 | + last_node = last_node.next |
| 23 | + last_node.next = new_node |
| 24 | + |
| 25 | + # Method to print the entire linked list for visualization |
| 26 | + def print_list(self): |
| 27 | + current_node = self.head |
| 28 | + nodes = [] |
| 29 | + while current_node: |
| 30 | + nodes.append(str(current_node.data)) |
| 31 | + current_node = current_node.next |
| 32 | + print(" -> ".join(nodes)) |
| 33 | + |
| 34 | + # Method to find the middle node of the linked list |
| 35 | + def find_middle(self): |
| 36 | + """ |
| 37 | + Finds the middle element of the linked list using the slow and fast pointer approach. |
| 38 | + """ |
| 39 | + if not self.head: |
| 40 | + print("The list is empty.") |
| 41 | + return None |
| 42 | + |
| 43 | + slow_pointer = self.head |
| 44 | + fast_pointer = self.head |
| 45 | + |
| 46 | + # Traverse the list until the fast pointer reaches the end |
| 47 | + while fast_pointer and fast_pointer.next: |
| 48 | + slow_pointer = slow_pointer.next |
| 49 | + fast_pointer = fast_pointer.next.next |
| 50 | + |
| 51 | + # At this point, the slow pointer is at the middle node |
| 52 | + return slow_pointer |
| 53 | + |
| 54 | +# --- Main Execution Block --- |
| 55 | +# This part of the code will run when you execute the script. |
| 56 | +if __name__ == "__main__": |
| 57 | + |
| 58 | + # --- Test Case 1: Odd Number of Elements --- |
| 59 | + print("--- Test Case 1: Odd List ---") |
| 60 | + ll_odd = LinkedList() |
| 61 | + for i in range(1, 6): |
| 62 | + ll_odd.append(i) # Creates 1 -> 2 -> 3 -> 4 -> 5 |
| 63 | + |
| 64 | + print("Input List:") |
| 65 | + ll_odd.print_list() |
| 66 | + middle_node_odd = ll_odd.find_middle() |
| 67 | + if middle_node_odd: |
| 68 | + print(f"The middle element is: {middle_node_odd.data}\n") # Expected: 3 |
| 69 | + |
| 70 | + # --- Test Case 2: Even Number of Elements --- |
| 71 | + print("--- Test Case 2: Even List ---") |
| 72 | + ll_even = LinkedList() |
| 73 | + for i in range(1, 7): |
| 74 | + ll_even.append(i) # Creates 1 -> 2 -> 3 -> 4 -> 5 -> 6 |
| 75 | + |
| 76 | + print("Input List:") |
| 77 | + ll_even.print_list() |
| 78 | + middle_node_even = ll_even.find_middle() |
| 79 | + if middle_node_even: |
| 80 | + print(f"The middle element is: {middle_node_even.data}\n") # Expected: 4 |
| 81 | + |
| 82 | + # --- Edge Case 3: Empty List --- |
| 83 | + print("--- Edge Case 3: Empty List ---") |
| 84 | + ll_empty = LinkedList() |
| 85 | + print("Input List: (empty)") |
| 86 | + middle_node_empty = ll_empty.find_middle() # Expected: "The list is empty." |
| 87 | + if not middle_node_empty: |
| 88 | + print("Correctly handled empty list.\n") |
| 89 | + |
| 90 | + # --- Edge Case 4: Single Node List --- |
| 91 | + print("--- Edge Case 4: Single Node List ---") |
| 92 | + ll_single = LinkedList() |
| 93 | + ll_single.append(42) # Creates 42 |
| 94 | + |
| 95 | + print("Input List:") |
| 96 | + ll_single.print_list() |
| 97 | + middle_node_single = ll_single.find_middle() |
| 98 | + if middle_node_single: |
| 99 | + print(f"The middle element is: {middle_node_single.data}\n") # Expected: 42 |
0 commit comments