use dummy node for linked list problems

Topics

• linked lists
• clean code
• algorithmic paradigm

Dummy nodes (also called sentinel or header nodes) are crucial for linked list problems because they eliminate several edge cases and simplify the code.

• Avoids Special Treatment of Head Node
• Simplifies Insert/Delete Operations
• Makes List Manipulation Safer

Caution

The only real downside is that you need to remember to return dummy.next instead of dummy when returning the list

A good example would be merging two sorted linked lists:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(-1), *curr = &dummy;
        
        while (l1 && l2){
            (l1->val < l2->val) ? (curr->next = l1, l1 = l1->next) 
                                : (curr->next = l2, l2 = l2->next);
            curr = curr->next;
        }
            
        curr->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

Without using this dummy node, we would need to check if curr is null before doing curr->next which would make the code look less clean.

Another nice example will be swapping nodes in pairs, i.e. for input [7, 8, 9, 10, 11]
we want output [8, 7, 10, 9, 11]:

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
 
        ListNode dummy(-1); // makes code simpler
        ListNode *prev = &dummy;
        ListNode *curr = head;
 
        while(curr and curr->next){
            prev->next = curr->next;
            curr->next = curr->next->next;
            prev->next->next = curr;
            prev = curr;
            curr = curr->next;    
        }
 
        return dummy.next;
    }
};

Related