MERGE TWO LINKED LISTS

Merge Two Sorted Linked Lists – Recursive Approach

Introduction

In this problem, we are given two sorted linked lists. The goal is to merge them into a single sorted linked list by rearranging the existing nodes.

This problem helps in understanding linked list traversal and recursion.

Problem Statement

Given two sorted linked lists list1 and list2:

  • Merge them into one sorted list

  • Do not create new nodes unnecessarily

  • Return the head of the merged list

Example

Input:

list1 = [1, 2, 4]
list2 = [1, 3, 4]

Output:

[1, 1, 2, 3, 4, 4]

Solution Code

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1 != null && list2 != null){
            if(list1.val < list2.val){
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            }
            else{
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }

        if(list1 == null)
            return list2;

        return list1;
    }
}

Approach Used: Recursion

Idea

At each step, we compare the current nodes of both lists:

  • Choose the smaller node

  • Recursively merge the remaining lists

How It Works

  1. Base condition:

    • If one list is empty = return the other list

  2. Compare values:

    • If list1.val < list2.val:

      • Attach list1 node

      • Recursively merge the rest

    • Else:

      • Attach list2 node

      • Recursively merge the rest

  3. Continue until all nodes are merged

Why This Approach Was Chosen

  • Code is clean and easy to understand

  • No need for extra data structures

  • Uses the natural recursive structure of linked lists

Alternative Approach

  • Iterative method (using loop)
     Avoids recursion stack
     Slightly more code

Why recursion here?
Because it makes the logic shorter and more intuitive.

Time and Space Complexity

  • Time Complexity: O(n + m)
    (n = length of list1, m = length of list2)

  • Space Complexity: O(n + m)
    (due to recursion stack)

Important Observation

  • We are not creating new nodes, just reusing existing ones

  • This is called in-place merging

  • The structure of linked list naturally fits recursion

Edge Cases

  • Both lists empty = return null

  • One list empty = return the other

  • Lists with duplicate values = handled correctly

Conclusion

The recursive approach provides a clean and elegant solution to merge two sorted linked lists. By comparing nodes step by step and building the result recursively, we efficiently merge both lists while maintaining sorted order.

 

Comments

Post a Comment

Popular posts from this blog

THE DELIVERY MAN

  The Delivery Man – Python List Operations  Introduction Lists in Python are used to store multiple items in a single variable. They are flexible, allowing us to add, remove, update, and manipulate elements easily. In this task, different list operations are performed to simulate a delivery man's workflow. 1. Creating a list and accessing an item items = ["Notebook", "Pencil", "Eraser", "Ruler", "Marker"] print(items[2]) Approach: Indexing Why: Lists use zero-based indexing, so the third item is accessed using index 2. 2. Adding a new item items.append("Glue Stick") print(items) Approach: append() method Why: It adds an item at the end of the list, which is ideal for adding new deliveries. 3. Inserting an item items.insert(2, "Highlighter") print(items) Approach: insert() method Why: Used when we need to add an item at a specific position instead of the end. 4. Removing an item items.remove("Ruler...
Read more

EC2 LAUNCHING

  EC2 Step 1: Launch EC2 Instance Go to: AWS Console --> EC2 --> Launch Instance Configure: Name : my-web-server AMI : Amazon Linux 2 (easy for beginners) Instance Type : t2.micro (free tier) Step 2: Key Pair Create or select a key pair. Step 3: Network Settings  Allow these: SSH (port 22) --> for login  HTTP (port 80) --> for web access Step 4: Launch Instance Click Launch Instance Step 5: Connect to Instance Use: EC2 --> Connect --> EC2 Instance Connect (easiest) OR via terminal: with this command. for this you have to download the pem files while selecting the key pair.  ssh -i your-key.pem ec2-user@<public-ip> Step 6: Install Web Server For Amazon Linux: sudo yum update -y sudo yum install httpd -y Step 7: Start Web Server sudo systemctl start httpd sudo systemctl enable httpd Step 8: Add a Web Page echo "Hello from EC2" | sudo tee /var/www/html/index.html Step 9: Get Public IP Go to EC2 d...
Read more

SORT A LINKED LIST USING MERGE SORT

  Sort a Linked List using Merge Sort Introduction Sorting a linked list efficiently is a common problem in data structures. Unlike arrays, linked lists do not allow direct access to elements, so algorithms like quicksort are not ideal. Merge Sort is the best choice for linked lists because: It does not require random access It works efficiently with node-based structures Problem Statement Given the head of a linked list: Sort the list in ascending order Return the sorted linked list Example Input: 10 -> 30 -> 20 -> 40 -> 60 -> 50 Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60 Solution Code class Solution: def mergeSort(self, head): if not head or not head.next: return head mid = self.getMiddle(head) next_to_mid = mid.next mid.next = None left = self.mergeSort(head) right = self.mergeSort(next_to_mid) return self.merge(left, right) def getMiddle(self,...
Read more