DAY 43: Solved Linked List Problems – Delete Node, Delete Middle, Palindrome, Odd-Even, Add Two Numbers | Linked List

---

🚀 Introduction

Welcome to Day 43 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 Singly Linked Lists, including: Delete Node in LL without head, Delete Middle Node of LL, Palindrome LL, Segregate Odd and Even Nodes in LL, and Add Two Numbers in LL.

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 40

• Delete Node in a Linked List
• Delete Middle Node of a Linked List

Day 41

• Palindrome Linked List
• Segregate Odd and Even Nodes in a Linked List

Day 42

• Add Two Numbers in a Linked List

Let’s dive into each of these topics in detail below 👇

---

Q 1. Delete Node in a Linked List:

We are given access to a node in the middle of a singly linked list (not the head or tail). Our task is to delete this node from the list.

Note: We do not have access to the head of the list.

Example:

Suppose the linked list is: 4 -> 5 -> 1 -> 9

• If we are given the node with value 5, after deletion, the linked list should look like:
  4 -> 1 -> 9

• If we are given the node with value 1, after deletion, the linked list should look like:
  4 -> 5 -> 9

Approach:

Since we cannot access the previous node, we cannot simply remove the node by changing the next pointer of the previous node.

Instead, we copy the value of the next node into the current node and then skip the next node.

Steps:

1. Store the next node of the given node.
2. Copy the val of the next node into the current node.
3. Point node.next to next.next to remove the next node.

This effectively deletes the given node without needing access to the head or previous node.

Code:

public void deleteNode(ListNode node) {
    ListNode nextNode = node.next;

    node.val = nextNode.val;
    node.next = nextNode.next;
}

Time & Space Complexity:

• Time Complexity: O(1)
  Only constant time operations are performed.

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

Final Thoughts:

• This is a classic trick question where you cannot traverse backward.
• The key insight is to replace the node’s value with its next node and delete the next node instead.
• This method works for all nodes except the last node in the list.

---

Q 2. Delete Middle Node of a Linked List:

In this problem, we are asked to delete the middle node of a singly linked list.

• If the linked list has odd length, remove the exact middle node.
• If the linked list has even length, remove the second middle node.
• Return the head of the modified linked list.

Example:

Consider a linked list with odd or even number of nodes.

Odd-length list:
Input: 1 -> 2 -> 3 -> 4 -> 5

• The middle node is 3.
• After deleting it, the linked list becomes:
  Output: 1 -> 2 -> 4 -> 5

Even-length list:
Input: 1 -> 2 -> 3 -> 4

• The two middle nodes are 2 and 3. By convention, we delete the second middle node, which is 3.
• The resulting list is:
  Output: 1 -> 2 -> 4

Approach:

1. Edge Case: If the list has only one node, return null.
2. Use the two-pointer technique:
   • slow pointer moves one step at a time.
   • fast pointer moves two steps at a time.
3. Maintain a prevSlow pointer to keep track of the node before slow.
4. When fast reaches the end, slow will be pointing to the middle node.
5. Delete the middle node by linking prevSlow.next to slow.next.
6. Return the modified head.

Code:

public ListNode deleteMiddle(ListNode head) {
    if(head.next == null) {
        return null;
    }

    ListNode slow = head;
    ListNode fast = head;
    ListNode prevSlow =  null;

    while(fast != null && fast.next != null) {
        prevSlow = slow;
        slow = slow.next;
        fast = fast.next.next;
    }

    prevSlow.next = slow.next;
    slow.next = null;

    return head;
}

Time & Space Complexity:

• Time Complexity: O(n)
  The list is traversed once using slow and fast pointers.

• Space Complexity: O(1)
  Only a few pointers are used; no extra data structures are required.

Final Thoughts:

• The slow and fast pointer technique efficiently finds the middle of a linked list in a single pass.
• Tracking the previous node (prevSlow) ensures the middle node can be deleted safely.
• This approach works seamlessly for both odd and even-length linked lists.

---

Q 3. Palindrome Linked List:

Check whether a given singly linked list is a palindrome, i.e., it reads the same forward and backward.

Example:

Input: 1 -> 2 -> 3 -> 2 -> 1
Output: true

Input: 1 -> 2 -> 3 -> 4
Output: false

Approach

1. Find the middle of the linked list using the slow and fast pointer technique.
2. Reverse the second half of the list.
3. Compare the first half and the reversed second half node by node.
4. Restore the list by reversing the second half back to its original order.
5. Return true if all corresponding nodes match; otherwise, return false.

Code:

public static boolean isPalindrome(Node head) {
    if(head == null || head.next == null) {
        return true;
    }

    Node mid = getMid(head);
    Node secondHalfHead = reverse(mid.next);

    Node first = head;
    Node second = secondHalfHead;
    boolean result = true;

    while (second != null) {
        if(first.value != second.value) {
            result = false;
            break;
        }
        first = first.next;
        second = second.next;
    }

    reverse(secondHalfHead);

    return result;
}

private static Node reverse(Node head) {
    Node prev = null;
    Node curr = head;

    while (curr != null) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

private static Node getMid(Node head) {
    Node slow = head;
    Node fast = head;

    while (fast != null && fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Time & Space Complexity:

• Time Complexity: O(n)
  Each node is visited at most twice (once for finding the middle and once for comparison).

• Space Complexity: O(1)
  No extra space is used; only pointers are manipulated.

Final Thoughts:

• Reversing the second half in-place allows checking for palindrome without extra memory.
• Restoring the list after the check preserves the original structure, which is useful in real applications.
• This approach efficiently handles both odd and even-length linked lists.

---

Q 4. Segregate Odd and Even Nodes in a Linked List:

In this problem, we are asked to rearrange a singly linked list such that all nodes at odd positions are grouped together followed by nodes at even positions. Note that the node positions are 1-indexed.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 3 -> 5 -> 2 -> 4

Input: 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
Output: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4

This ensures all nodes at odd indices come first, followed by nodes at even indices, preserving relative order within odd and even nodes.

Approach:

1. Initialize two pointers:
   • odd pointing to the first node
   • even pointing to the second node
   • Store evenStart to remember the head of the even nodes
2. Traverse the list and link all odd nodes together, then all even nodes together.
3. After processing all nodes, link the last odd node to the evenStart.
4. Return the updated head of the list.

Code:

public static Node oddEvenList(Node head) {
    if(head == null || head.next == null) {
        return head;
    }
    Node odd = head;
    Node even = head.next;
    Node evenStart = even;

    while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;

        even.next = odd.next;
        even = even.next;
    }

    odd.next = evenStart;

    return head;
}

Time & Space Complexity:

• Time Complexity: O(n)
  The list is traversed once.

• Space Complexity: O(1)
  Only a few pointers are used; no extra data structures.

Final Thoughts:

• Using two pointers efficiently separates odd and even nodes in a single traversal.
• The relative order of nodes within the odd and even groups is maintained.
• This is an in-place algorithm, requiring no extra memory, making it optimal for large linked lists.

---

Q 5. Add Two Numbers in a Linked List:

Given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

This is a classic Linked List + Math problem also available on LeetCode (Problem 2: Add Two Numbers).

Example:

Input:
head1 = 2 -> 4 -> 3 (represents 342)
head2 = 5 -> 6 -> 4 (represents 465)

Output:
7 -> 0 -> 8 (represents 807)

Explanation: 342 + 465 = 807. Since the digits are stored in reverse order, the result is represented as 7 -> 0 -> 8.

Approach:

1. Initialize two pointers (temp1, temp2) to traverse both linked lists.
2. Use a dummy node and a curr pointer to build the result list.
3. Maintain a carry variable (initially 0).
4. At each step:
   • Add corresponding digits from temp1 and temp2 along with carry.
   • Update carry = sum / 10 and the current node value as sum % 10.
5. Move pointers forward until both lists are fully traversed.
6. If there is a leftover carry after traversal, add a new node with that carry.
7. Return dummy.next as the head of the new list.

Code:

public static Node addTwoNumbers(Node head1, Node head2) {
    Node temp1 = head1;
    Node temp2 = head2;

    Node dummy = new Node(-1);
    Node curr = dummy;
    int carry = 0;

    while (temp1 != null || temp2 != null) {
        int sum = carry;

        if (temp1 != null) {
            sum += temp1.value;
            temp1 = temp1.next;
        }

        if (temp2 != null) {
            sum += temp2.value;
            temp2 = temp2.next;
        }

        carry = sum / 10;
        sum = sum % 10;

        Node node = new Node(sum);
        curr.next = node;
        curr = node;
    }

    if (carry > 0) {
        curr.next = new Node(carry);
    }

    return dummy.next;
}

Time & Space Complexity:

• Time Complexity: O(max(m, n))
  We iterate through both linked lists once, where m and n are their lengths.

• Space Complexity: O(max(m, n))
  A new linked list is created to store the result.

Final Thoughts:

• This problem demonstrates how to simulate addition manually while handling carry values.
• Using a dummy node simplifies list creation by avoiding edge case handling for the head.
• This solution is optimal since we only traverse each list once and build the result in a single pass.
• It is a must-practice problem for mastering Linked List manipulations combined with basic arithmetic.

---

6. 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!

---

7. Conclusion:

In this blog of my DSA journey, we explored five important problems that not only strengthen our understanding of Linked Lists but also improve our problem-solving skills:

• Delete a Node without Head Reference – A clever trick where we replace values instead of traversing backward.
• Delete Middle Node of a Linked List – Using slow & fast pointers to efficiently locate and remove the middle.
• Palindrome Linked List – Reversing the second half to check symmetry in O(1) space.
• Segregate Odd and Even Nodes – Rearranging nodes in-place while maintaining relative order.
• Add Two Numbers in Linked List – Simulating addition with carry using linked list traversal.

These problems highlight the versatility of pointer manipulation techniques (like slow & fast pointers, in-place reversal, and pointer re-linking), which form the backbone of solving linked list challenges.

By practicing these, I’ve built a stronger foundation in handling edge cases, in-place modifications, and traversal strategies, all of which are crucial for advanced linked list problems.

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