Day 34: Solved Insert using Recursion, Remove Nodes, Remove Duplicates, and Merge Sorted Lists Problems | Linked List

---

🚀 Introduction

Welcome to Day 34 of my DSA Journey!
After wrapping up an intense few weeks focused on Recursion, I’ve recently shifted my focus to one of the most fundamental data structures in DSA — the Linked List.

Moving from recursion to linked lists has been a rewarding transition since these concepts are closely related, especially when dealing with problems involving traversal and pointer manipulation.

Over the past 3 days, I’ve solved several important problems on the Singly Linked List, including inserting nodes using recursion, removing elements, removing duplicates from a sorted list, and merging two sorted lists.

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

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

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

Day 31

• Insert at a Particular Index Using Recursion
• Remove Linked List Elements

Day 32

• Remove Duplicates from a Sorted List

Day 33

• Merge Two Sorted Lists

Let’s dive into each of these topics below 👇

---

Q 1. Insert at a Particular Index Using Recursion:

Given a singly linked list, insert a new node with a given value val at a specified index index using recursion.

• If index is 0, the new node should become the new head of the list.
• Otherwise, recursively traverse the list until you reach the correct position, and insert the node there.

Example:

Suppose the linked list is:
1 -> 3 -> 5 -> 7 -> null

If we insert value 4 at index 2, the updated list should be:
1 -> 3 -> 4 -> 5 -> 7 -> null

Explanation:

• The node with value 4 is inserted between nodes 3 and 5.
• Indexing is zero-based, so index 2 refers to the third position in the list.

Approach:

• Use a recursive helper function that takes the current node and the current index.
• Base case: When index is 0, create a new node with the given value and point its next to the current node.
• Recursive case: Reduce index by 1 and recursively call the function on the next node.
• Re-link nodes properly on the way back from recursion to maintain the list structure.
• Update the head pointer when the new node is inserted at the beginning.

Code:

public void insertRec(int index, int val) {
    head = insertRec(index, val, head);
}

private Node insertRec(int index, int val, Node node) {
    if (index == 0) {
        Node temp = new Node(val, node);
        size++;
        return temp;
    }
    node.next = insertRec(index - 1, val, node.next);
    return node;
}

Time & Space Complexity:

• Time Complexity: O(n)
  Because in the worst case, we recursively traverse the list up to the insertion index.

• Space Complexity: O(n)
  Due to recursive call stack usage proportional to the depth of recursion (up to index).

Final Thoughts:

• Recursion provides an elegant way to solve linked list insertion problems, especially when managing node references carefully.
• This approach neatly handles insertion at any position, including the head of the list.
• However, be cautious with recursion depth for very large lists as it may cause stack overflow; an iterative approach could be more practical in such cases.

---

Q 2. Remove Linked List Elements:

Given a singly linked list, remove all nodes that have a specific value val.

• Traverse the linked list and delete every node whose value matches val.
• Return the updated head of the list after all such nodes have been removed.

Example:

Suppose the linked list is:
1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> null

If we remove all nodes with value 6, the updated list should be:
1 -> 2 -> 3 -> 4 -> 5 -> null

Explanation:

• Both nodes containing the value 6 are removed.
• The rest of the list remains intact and properly linked.

Approach:

• Use a dummy node pointing to the head to handle edge cases, such as deleting the head node(s).
• Use two pointers: prev (initially dummy) and curr (initially head).
• Traverse the list with curr:
  • If curr.value equals val, update prev.next to skip curr (removing it).
  • Otherwise, move prev to curr.
• Always move curr forward to continue traversal.
• Return dummy.next as the new head of the updated list.

Code:

private Node removeElements(Node head, int val) {
    if (head == null) {
        return null;
    }

    Node dummy = new Node(-1);
    dummy.next = head;
    Node prev = dummy;
    Node curr = head;

    while (curr != null) {
        if (curr.value == val) {
            prev.next = curr.next;
        } else {
            prev = prev.next;
        }
        curr = curr.next;
    }

    return dummy.next;
}

Time & Space Complexity:

• Time Complexity: O(n)
  We traverse the list once, checking each node’s value.

• Space Complexity: O(1)
  We use a constant amount of extra space (dummy node and pointers).

Final Thoughts:

• The dummy node technique simplifies edge cases, such as removing nodes at the head.
• Using two pointers allows efficient removal without breaking list integrity.
• This iterative approach is straightforward and avoids recursive stack overhead.
• Always ensure the list remains properly linked after deletions to prevent broken chains.

---

Q 3. Remove Duplicates from a Sorted List:

Given a sorted singly linked list, remove all duplicate nodes such that each element appears only once.

Since the list is sorted, any duplicates will be adjacent.
The goal is to traverse the list once and remove consecutive nodes with the same value.

Example:

Suppose the linked list is:
1 -> 1 -> 2 -> 3 -> 3 -> 4 -> null

After removing duplicates, the list should become:
1 -> 2 -> 3 -> 4 -> null

Approach:

• Use two pointers: prev (starting at head) and curr (starting at head.next).
• Iterate over the list with curr.
• If curr.val is different from prev.val, link prev.next to curr and move prev forward.
• If curr.val is the same as prev.val, skip curr by moving it forward without updating prev.
• After the loop, set prev.next to null to remove any trailing duplicates.

Code:

private void removeDuplicates(ListNode head){
    if(head == null) {
        return;
    }
    ListNode prev = head;
    ListNode curr = head.next;

    while(curr != null) {
        if(curr.val != prev.val){
            prev.next = curr;
            prev = curr;
        }
        curr = curr.next;
    }
    prev.next = null;
}

Time & Space Complexity:

• Time Complexity: O(n)
  We traverse the list once, comparing adjacent nodes.

• Space Complexity: O(1)
  No extra space is used except pointers.

Final Thoughts:

• This approach efficiently removes duplicates in a sorted list by leveraging the sorted order.
• Using two pointers avoids unnecessary extra data structures.
• Always remember to terminate the list properly after removal to prevent dangling nodes.
• This in-place method preserves the original list structure without additional memory overhead.

---

Q 4. Merge Two Sorted Lists:

Given two sorted linked lists, merge them into a single sorted linked list.

Given head of two linked lists list1 and list2 that are already sorted in non-decreasing order.
Our task is to merge these two lists into one sorted list and return the merged list.

Example:

list1: 1 -> 3 -> 5 -> null
list2: 2 -> 4 -> 6 -> null
Merged list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Approach:

• Create a dummy node that will act as the head of the merged list.
• Maintain a pointer temp that points to the last node in the merged list.
• Traverse both lists simultaneously, comparing current nodes.
• Attach the smaller node to temp.next and advance in that list.
• Move temp forward after each insertion.
• When one list is exhausted, append the remaining nodes from the other list.
• Return the merged list starting from dummy.next.

Code:

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode();
    ListNode temp = dummy;

    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            temp.next = list1;
            list1 = list1.next;
        } else {
            temp.next = list2;
            list2 = list2.next;
        }
        temp = temp.next;
    }

    if (list1 != null) {
        temp.next = list1;
    } else {
        temp.next = list2;
    }

    return dummy.next;
}

Time & Space Complexity:

• Time Complexity: O(n + m)
  Where n and m are the lengths of the two lists. Each node is visited once.

• Space Complexity: O(1)
  The merging is done in-place without extra data structures.

Final Thoughts:

• Using a dummy node simplifies edge cases and makes the code cleaner.
• This approach efficiently merges two sorted lists in a single pass.
• Since nodes are reused without creating new ones, memory usage is minimal.
• This method is ideal for merging linked lists in many real-world applications.

---

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 of my dsa journey, I tackled four important linked list problems that deepen the understanding of pointer manipulation and recursive as well as iterative approaches in linked lists:

• Insert at a Particular Index Using Recursion: Showed how recursion can elegantly handle node insertion at any position, including the head.
• Remove Linked List Elements: Demonstrated a robust iterative approach using a dummy node to simplify edge cases while removing specified values.
• Remove Duplicates from Sorted List: Leveraged the sorted property to efficiently remove duplicates in-place with two pointers.
• Merge Two Sorted Lists: Illustrated an optimal in-place merging technique using a dummy node for clean and efficient combination of two sorted linked lists.

Working through these problems has reinforced key concepts like recursion, iteration, dummy nodes, and pointer updates, which are foundational to mastering linked lists.

These exercises also highlight the importance of carefully maintaining list integrity to avoid broken chains or memory leaks.

As I continue my DSA journey, I look forward to applying these concepts to more complex problems and data structures. If you're learning alongside me, keep practicing these fundamental techniques — they form the building blocks for solving more advanced challenges.

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