Learning

Linked Lists

Linked Lists

Singly Linked List

python
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 not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node def prepend(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def delete(self, data): if not self.head: return if self.head.data == data: self.head = self.head.next return current = self.head while current.next: if current.next.data == data: current.next = current.next.next return current = current.next def __str__(self): nodes = [] current = self.head while current: nodes.append(str(current.data)) current = current.next return ' -> '.join(nodes) + ' -> None' ll = LinkedList() ll.append(1) ll.append(2) ll.prepend(0) print(ll) # 0 -> 1 -> 2 -> None ll.delete(1) print(ll) # 0 -> 2 -> None

Fast & Slow Pointers (Cycle Detection)

python
def has_cycle(head): if not head: return False slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False # Create cycle n1 = Node(1) n2 = Node(2) n3 = Node(3) n1.next = n2 n2.next = n3 n3.next = n1 # Cycle! print(has_cycle(n1)) # True

Reverse Linked List

python
def reverse(head): prev = None current = head while current: next_node = current.next current.next = prev prev = current current = next_node return prev

Dummy Head Technique

python
def delete_all(head, val): dummy = Node(0) # Sentinel node dummy.next = head current = dummy while current.next: if current.next.data == val: current.next = current.next.next else: current = current.next return dummy.next

Find Middle Element

python
def find_middle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow.data
Key Rules
  • •Linked list nodes have data + next pointer — no random access, must traverse from head
  • •Singly linked list: O(1) insert at head, O(n) insert at tail (unless you keep a tail pointer)
  • •Dummy head (sentinel node) eliminates edge cases for head deletion/insertion
  • •Fast & slow pointers: fast moves 2 steps, slow moves 1 — finds middle or detects cycles in O(n)
  • •Reverse: iteratively swap next direction using 3 pointers (prev, current, next)
  • •Linked lists have O(n) access time but O(1) insertion/deletion at known positions (no shifting!)
Your Task

Implement a `SinglyLinkedList` class with `Node` inner class. Methods: `append(data)`, `prepend(data)`, `delete(data)` (first occurrence), `reverse()`, `find_middle()`, `has_cycle()`, `__str__`, and `to_list()`. Also implement `merge_sorted(l1, l2)` that merges two sorted linked lists into a new sorted list. Demonstrate: build list, reverse it, find middle, detect cycle (create one), and merge two sorted lists.

EditorPython · JSX
PreviewUpdates on Run Tests
Loading preview…
Tests
Should define Stack class with push and pop
Should define Queue class using deque
Queue should use popleft for dequeue
Should implement next_greater_element with stack
Should implement is_balanced with stack
Should import deque from collections