3. Linked Lists (Days 30—44)

Reverse Linked List

def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Merge Two Sorted Lists

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1; l1 = l1.next
        else:
            tail.next = l2; l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Linked List Cycle (Floyd's Algorithm)

// C++ — Tortoise & Hare
bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

More Problems

Problem	Pattern	Complexity
Palindrome Linked List	Find mid, reverse second half	O(n), O(1)
Intersection of Two Lists	Two pointers, switch heads	O(n), O(1)
Add Two Numbers	Dummy node, carry	O(n), O(n)
Copy List with Random Pointer	Interleaved nodes, hash map	O(n), O(n)

✏️ Exercise: Implement Reverse Linked List (iterative + recursive), then solve Merge Two Sorted Lists. Use Floyd's algorithm to detect a cycle in a custom list.