102 Dummy references (or dummy nodes) in LinkedList

What is a dummy node?

A dummy node is a placeholder node used as the starting point of a new linked list.
It often has a value like -1 or 0, and its main purpose is not for storing data but to help simplify code logic.

---

Why use a dummy node?

• To avoid handling special cases when dealing with the head of the list.

• To build a new list easily without checking if it’s the first node.

• To simplify pointer manipulation (especially useful in deletion or partitioning problems).

• Prevents null pointer exceptions during iteration or insertion.

Common Scenarios / Use Cases

1. Merging Two Sorted Linked Lists

You don’t know which node will be the head of the merged list, so using a dummy node allows you to build the merged list without worrying about head initialization.

dummy = ListNode(-1)
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



2. Removing N-th Node from End
You might need to remove the head node; a dummy helps you unify logic regardless of which node is removed.
3. Partitioning Linked List (e.g., around a value x)
You use two dummy nodes to form two separate lists (less-than and greater-than) and later combine them.


    less_dummy = ListNode(-1)
    more_dummy = ListNode(-1)
    less = less_dummy
    more = more_dummy

    while head:
        if head.val < x:
            less.next = head
            less = less.next
        else:
            more.next = head
            more = more.next
        head = head.next

    # Combine the lists
    less.next = more_dummy.next
    more.next = None
    return less_dummy.next

4. Detect and Remove a Loop
When removing the loop, using a dummy node helps when the loop includes the head node.

5. Reversing Nodes in K-Group
When reversing nodes in chunks of k, the dummy node helps track the new head as well as the tail pointer of the previous block.

6. Flattening Multilevel Linked Lists
When recursively or iteratively building a flattened list, a dummy node can be used as the start of the result list.