DAY 49: Mastering Doubly Linked List Problems – Reverse, Delete Key, Pair Sum & Remove Duplicates | Linked List

---

🚀 Introduction

Welcome to Day 49 of my DSA Journey!
After spending an intense few weeks focusing on Recursion, I’ve now shifted my attention to one of the most fundamental data structures in DSA — the Linked List.

Transitioning from recursion to linked lists has been a rewarding step, as these concepts are closely connected, especially when solving problems involving traversal and pointer manipulation.

Over the past 3 days, I’ve solved several key problems on Doubly Linked Lists, including: Reverse a DLL, Delete all occurrences of a key in DLL, Find pairs with a given sum in DLL, and
Remove duplicates from a sorted DLL.

I’m sharing this journey publicly to stay consistent and to help others who are starting their DSA path from scratch.

Feel free to follow me on Twitter for real-time updates and coding insights!

📅 Here’s What I Covered Over the Last 3 Days:

Day 46

• Reverse a Doubly Linked List
• Delete all occurrences of a key in DLL

Day 47

• Find pairs with a given sum in DLL

Day 48

• Remove duplicates from a sorted DLL

Let’s dive deeper into these problems below 👇

---

Q 1. Reverse a Doubly Linked List

Given the head of a Doubly Linked List (DLL), our task is to reverse the linked list. That means the head should become the tail, and the tail should become the head, while keeping the next and prev pointers consistent.

Example:

Input (Original DLL): 1 <-> 2 <-> 3 <-> 4

Output (Reversed DLL): 4 <-> 3 <-> 2 <-> 1

As we can see, the links between nodes are reversed:

• Node 1 which was the head becomes the tail.
• Node 4 which was the tail becomes the new head.

Approach:

1. Traverse the list using a pointer curr.
2. For each node:
   • Swap the next and prev pointers.
   • Move forward using the original next (stored in nextNode).
3. Keep track of the previous node (prevNode), which will eventually become the new head.
4. Return prevNode at the end.

Code Implementation:

public static Node reverseDLL(Node head) {
    if (head == null || head.next == null) {
        return head;    // empty list or single node
    }

    Node curr = head;
    Node prevNode = null;

    while (curr != null) {
        Node nextNode = curr.next;

        // Swap pointers
        curr.prev = nextNode;
        curr.next = prevNode;

        // Move forward
        prevNode = curr;
        curr = nextNode;
    }

    return prevNode; // New head
}

Time & Space Complexity:

• Time Complexity: O(n) → We traverse the list once.
• Space Complexity: O(1) → No extra space used, just a few pointers.

Final Thoughts:

Reversing a Doubly Linked List is all about carefully swapping pointers.

• Unlike a Singly Linked List, DLLs give us more flexibility because of the prev pointer.
• This approach ensures we do everything in-place, with no extra memory overhead.

---

Q 2. Delete All Occurrences of a Key in Doubly Linked List

Given a Doubly Linked List (DLL), delete all the nodes that contain a given key.

Example:

Input:
DLL = 1 <-> 2 <-> 3 <-> 2 <-> 4, key = 2

Output:
1 <-> 3 <-> 4

Here, all nodes with value 2 are removed.

Approach:

1. Traverse the DLL node by node.
2. For each node that matches the key:
   • If it’s the head, move the head pointer forward.
   • If it’s a middle node, adjust prev.next and next.prev to bypass the current node.
   • If it’s the last node, simply update the prev.next to null.
3. Continue until the end of the list.
4. Return the updated head.

Code Implementation:

private static Node delete(Node head, int key) {
    if (head == null) return null;

    Node temp = head;
    while (temp != null) {
        Node prevNode = temp.prev;
        Node nextNode = temp.next;

        if (temp.value == key && temp == head) {
            head = nextNode;
            if (head != null) {
                head.prev = null;
            }
        } else if (temp.value == key) {
            prevNode.next = nextNode;
            if (nextNode != null) {
                nextNode.prev = prevNode;
            }
        }

        temp = nextNode;
    }

    return head;
}

Time & Space Complexity:

• Time Complexity: O(n) → We traverse the entire list once.
• Space Complexity: O(1) → Only a few extra pointers are used.

Final Thoughts:

• Deleting nodes in a Doubly Linked List is easier than in a Singly Linked List because we have access to both prev and next.
• Special care is required when deleting the head node or the last node.
• This approach ensures we handle all occurrences of the key efficiently in one traversal.

---

Q 3. Find pairs with a given sum in DLL

Given a sorted Doubly Linked List (DLL) and an integer sum, the task is to find all pairs of nodes whose values add up to the given sum.

Example:

Input:
DLL = 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 6
sum = 7

Output:
[1, 6], [2, 5], [3, 4]

Explanation:
All these pairs add up to 7.

Approach:

1. Use two pointers:

   • start → beginning of the DLL.
   • end → last node of the DLL.

2. Move end pointer to the last node.

3. Traverse until start.value < end.value:

   • If start.value + end.value == sum → store the pair and move both pointers inward.
   • If sum is smaller → move start forward.
   • If sum is larger → move end backward.

This approach works because the DLL is sorted.

Code Implementation:

private static List<List<Integer>> pairSum(Node head, int sum){
    List<List<Integer>> ans = new ArrayList<>();
    if(head == null || head.next == null){
        return ans;
    }

    Node start = head;
    Node end = head;
    while (end.next != null) {
        end = end.next;
    }

    while (start.value < end.value) {
        int total = start.value + end.value;
        if(total > sum){
            end = end.prev;
        } else if(total < sum){
            start = start.next;
        } else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(start.value);
            list.add(end.value);
            ans.add(list);
            end = end.prev;
            start = start.next;
        }
    }

    return ans;
}

Time & Space Complexity:

• Time Complexity: O(n) → Each pointer traverses the list at most once.
• Space Complexity: O(1) → Apart from the answer list, only pointers are used.

Final Thoughts:

• This is a two-pointer approach adapted for a DLL.
• Using both prev and next makes moving pointers in both directions very convenient.
• Works efficiently in one traversal without extra space.

---

Q 4. Remove duplicates from a sorted DLL

We are given a sorted doubly linked list (DLL), and we need to remove all duplicate nodes so that only distinct values remain.

Example:

Input DLL:
1 ⇄ 2 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 4 ⇄ 4 ⇄ 5

Output DLL:
1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5

Here, duplicates (2 and 4) are removed, and only unique values are kept.

Approach:

1. Since the DLL is sorted, duplicates will always appear consecutively.
2. Traverse the list node by node:
   • Use a pointer (temp) to check the next nodes.
   • Skip all nodes that have the same value as the current node.
   • Update both next and prev pointers to maintain DLL structure.
3. Continue until the end of the list.

Code Implementation:

private static Node removeDuplicates(Node head) {
    Node temp = head;
    while (temp != null && temp.next != null) {
        Node nextNode = temp.next;

        // Skip all duplicates
        while (nextNode != null && nextNode.value == temp.value) {
            nextNode = nextNode.next;
        }

        // Update links
        temp.next = nextNode;
        if (nextNode != null) {
            nextNode.prev = temp;
        }

        // Move forward
        temp = temp.next;
    }
    return head;
}

Time & Space Complexity:

• Time Complexity: O(n) → We traverse the list once.
• Space Complexity: O(1) → No extra space used, only pointers.

Final Thoughts:

• Since the DLL is sorted, duplicates are easy to detect consecutively.
• Updating both next and prev pointers ensures proper DLL structure.
• This approach is efficient, in-place, and avoids extra memory usage.

---

5. What's next:

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

6. Conclusion:

In this blog, we explored some of the most fundamental problems on Doubly Linked Lists (DLLs):

• 🔄 Reversing a DLL
• ❌ Deleting all occurrences of a key
• 🔍 Finding pairs with a given sum
• 🧹 Removing duplicates from a sorted DLL

Each of these problems highlights the power of the prev pointer in DLLs, which makes operations more flexible compared to Singly Linked Lists.

The key takeaways are:

• Efficient pointer manipulation is the core of DLL problems.
• Most operations can be done in-place with O(1) space.
• Understanding traversal in both directions opens up elegant approaches (like the two-pointer technique).

Mastering these builds a strong foundation for solving more advanced linked list problems, including circular DLLs and real-world applications like LRU Cache, text editors, and navigation history.

If you're on a similar learning path, feel free to follow along or reach out — let’s grow together.