DAY 46: Solved Linked List Problems – Sort, 0-1-2 Sort, Intersection, Add 1 to a Number | Linked List

---

🚀 Introduction

Welcome to Day 46 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: Sort Linked List, Sort a LL of 0's 1's and 2's, Intersection of Two Linked Lists, and Add 1 to a number represented by 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 43

• Sort Linked List
• Sort a LL of 0's 1's and 2's

Day 44

• Intersection of Two Linked Lists

Day 45

• Add 1 to a number represented by LL

Let’s dive deeper into these problems below 👇

---

Q 1. Sort Linked List

Given the head of a singly linked list, the task is to sort the list in ascending order. Unlike arrays, where random access is possible, linked lists require pointer manipulation, making sorting more challenging.

Example:

Input: 4 → 2 → 1 → 3

Output: 1 → 2 → 3 → 4

We want to rearrange the nodes of the linked list so that values are in sorted order.

Approach:

The most efficient way to sort a linked list is to use Merge Sort because:

• Merge sort works very well with linked lists (no need for extra space like arrays).
• Quick Sort is not efficient here due to random access requirements.

Steps:

1. Find the Middle Node using slow and fast pointer (to divide the list into halves).
2. Recursively Apply Merge Sort on left and right halves.
3. Merge Two Sorted Lists into one sorted linked list.

How It Works?

1. Split the linked list into two halves using getMid.
2. Recursively sort both halves with mergeSort.
3. Use mergeTwoSortedList to merge them into a sorted linked list.

This is the classic Divide and Conquer approach.

Code:

public static Node mergeSort(Node head) {
    if (head == null || head.next == null) {
        return head; // Base case
    }

    // Step 1: Split the list into two halves
    Node mid = getMid(head);

    // Step 2: Recursively sort both halves
    Node left = mergeSort(head);
    Node right = mergeSort(mid);

    // Step 3: Merge the two sorted halves
    return mergeTwoSortedList(left, right);
}

private static Node mergeTwoSortedList(Node head1, Node head2) {
    Node dummy = new Node(-1);
    Node temp = dummy;

    Node temp1 = head1;
    Node temp2 = head2;

    while (temp1 != null && temp2 != null) {
        if (temp1.value <= temp2.value) {
            temp.next = temp1;
            temp1 = temp1.next;
        } else {
            temp.next = temp2;
            temp2 = temp2.next;
        }
        temp = temp.next;
    }

    // Attach remaining nodes
    if (temp1 != null) {
        temp.next = temp1;
    } else {
        temp.next = temp2;
    }

    return dummy.next;
}

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

    // Move slow by 1 and fast by 2 steps
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }

    // Disconnect the left half from the right half
    if (prev != null) {
        prev.next = null;
    }
    return slow;
}

Time & Space Complexity:

Time Complexity:

• Each split takes O(log N) (like merge sort).
• Merging takes O(N).
• Overall: O(N log N)

Space Complexity:

• O(log N) due to recursive call stack.
• No extra array space is needed (unlike array-based merge sort)

Final Thoughts:

• Sorting a linked list is a perfect use-case for Merge Sort.
• It avoids extra memory overhead.
• It ensures a guaranteed O(N log N) performance.
• By breaking the list into halves and merging efficiently, we achieve a clean, recursive solution.

---

Q 2. Sort a LL of 0's 1's and 2's

Given a singly linked list containing only 0's, 1's, and 2's, sort the linked list in-place so that all 0's appear first, followed by 1's, and then 2's.

Example:

Input: 1 -> 2 -> 0 -> 1 -> 2 -> 0

Output: 0 -> 0 -> 1 -> 1 -> 2 -> 2

Explanation:

• The original list has nodes with values 1, 2, 0, 1, 2, 0 in an unsorted order.
• After sorting, all 0's come first, followed by all 1's, and then all 2's, maintaining the correct order of values.
• This demonstrates how the algorithm groups nodes based on their value efficiently without swapping individual data.

Approach:

1. Create three dummy nodes to represent separate lists for 0's, 1's, and 2's.
2. Traverse the original list and append each node to the corresponding list based on its value.
3. Link the three lists together in the order 0 → 1 → 2.
4. Ensure the last node of the 2's list points to null.
5. Return the head of the new sorted list (dummyZero.next).

This approach avoids data swapping and works in a single pass with constant extra space.

Code:

private static Node sort(Node head) {
    if(head == null || head.next == null) {
        return head;
    }

    Node dummyZero = new Node(-1);
    Node dummyOne = new Node(-1);
    Node dummyTwo = new Node(-1);
    Node zero = dummyZero;
    Node one = dummyOne;
    Node two = dummyTwo;

    Node temp = head;
    while (temp != null) {
        if(temp.value == 0){
            zero.next = temp;
            zero = temp;
        } else if(temp.value == 1) {
            one.next = temp;
            one = temp;
        } else {
            two.next = temp;
            two = temp;
        }
        temp = temp.next;
    }

    // Link Zero & One lists
    if(dummyOne.next != null) {
        zero.next = dummyOne.next;
        one.next = dummyTwo.next;
    } else {
        zero.next = dummyTwo.next;
    }

    // Terminate Two list
    two.next = null;

    return dummyZero.next;
}

Time & Space Complexity:

Time Complexity:

• Single traversal of the list → O(N)

Space Complexity:

• Constant extra space for dummy nodes → O(1)

Final Thoughts:

• This problem demonstrates an efficient way to sort a limited-range linked list without comparing or swapping values.
• By dividing nodes into separate lists and merging them, we achieve a single-pass solution with minimal space.
• It’s an excellent example of how pointer manipulation can simplify in-place sorting problems in linked lists.

---

Q 3. Intersection of Two Linked Lists

Given two singly linked lists, find the node at which the two lists intersect.
If the linked lists do not intersect, return null.

Example:

Input:
List1: 1 -> 3 -> 5 -> 7 -> 9 -> 11
List2: 2 -> 4 -> 9 -> 11
Output: 9

Explanation:
The two linked lists merge at the node with value 9. From that point onward, both lists share the same nodes.

Approach:

We use a two-pointer technique:

1. Initialize two pointers, temp1 at head1 and temp2 at head2.
2. Traverse both lists simultaneously.
3. If a pointer reaches the end of its list, redirect it to the head of the other list.
4. Continue until the two pointers meet at the intersection or both reach null.

This ensures that both pointers traverse the same total length and will meet at the intersection if it exists.

Code:

public Node intersectPoint(Node head1, Node head2) {
    if(head1 == null || head2 == null) {
        return null;
    }

    Node temp1 = head1;
    Node temp2 = head2;

    while(temp1 != temp2){
        temp1 = temp1.next;
        temp2 = temp2.next;

        if(temp1 == temp2) return temp1;

        if(temp1 == null) temp1 = head2;
        if(temp2 == null) temp2 = head1;
    }

    return temp1;
}

Time & Space Complexity:

Time Complexity:
O(N + M), where N and M are the lengths of the two linked lists.

Space Complexity:
O(1), only two pointers are used.

Final Thoughts:

• This problem highlights the power of the two-pointer technique for linked lists.
• By cleverly redirecting pointers, we can find the intersection without extra memory or computing list lengths.
• It’s an elegant solution that guarantees a single traversal of both lists.

---

Q 4. Add 1 to a number represented by a Linked List

This problem requires adding 1 to a number represented by a linked list, where each node contains a single digit. The most significant digit is at the head of the list.

Example:

Input: 1 -> 2 -> 9
Output: 1 -> 3 -> 0

Explanation:
The linked list represents the number 129.

• Start adding 1 from the last node (least significant digit): 9 + 1 = 10 → set node value to 0, carry = 1.
• Move to the next node: 2 + carry = 3 → set node value to 3, carry = 0.
• The head node remains 1.

Final linked list: 1 -> 3 -> 0, which represents the number 130.
This example clarifies that the addition propagates from the end towards the head, properly handling carry-over.

Approach:

1. Use recursion to traverse to the end of the linked list.
2. Start adding 1 from the last node (least significant digit).
3. Maintain a carry as you move backward through the recursion.
4. If there's a remaining carry after processing the head, create a new node at the beginning.

Code:

private static Node addOne(Node head) {
    if(head == null) {
        return new Node(1);
    }

    int carry = helper(head);

    if(carry == 1) {
        Node node = new Node(1);
        node.next = head;
        head = node;
    }

    return head;
}

private static int helper(Node temp) {
    if(temp == null) {
        return 1;
    }

    int carry = helper(temp.next);
    temp.value = temp.value + carry;
    if(temp.value >= 10){
        temp.value = 0;
        carry = 1;
    } else {
        carry = 0;
    }

    return carry;
}

Time & Space Complexity:

Time Complexity:
O(N), where N is the length of the linked list.

Space Complexity:
O(N) due to recursive call stack.

Final Thoughts:

• This problem demonstrates a recursive approach for in-place arithmetic on linked lists.
• By processing from least significant digit to most significant, we efficiently handle carry propagation.
• It’s a neat example of combining recursion with linked list manipulation to solve arithmetic problems.

---

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:

Over the last few days of my DSA journey, I’ve explored some essential Linked List problems that combine recursion, pointer manipulation, and in-place data handling.

Here’s a quick recap of what I learned:

• Sort Linked List → Leveraged Merge Sort to sort a linked list efficiently in O(N log N) time.
• Sort a LL of 0's, 1's, and 2's → Used dummy nodes and pointer manipulation for a single-pass O(N) solution.
• Intersection of Two Linked Lists → Applied the two-pointer technique to detect intersection in O(N + M) time with O(1) space.
• Add 1 to a number represented by a LL → Combined recursion with linked list traversal to handle carry propagation elegantly.

These problems reinforced important Linked List concepts: recursion, traversal, pointer handling, and divide-and-conquer strategies.

Key takeaway:
Linked Lists may seem simple, but they offer rich opportunities to practice problem-solving techniques that scale to more complex data structures and algorithms.

As I continue this journey, I’ll be exploring more advanced Linked List problems, stack and queue implementations, and dynamic programming challenges.

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