Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
In-place Merge Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.3.
Implementation in Python
2.3.1.
Time Complexity
2.3.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
Why is the space complexity of the above approach O(1)?
3.2.
Is merge sort in-place for linked lists?
3.3.
Why do we prefer merge sort in linked lists?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

In-place Merge two Linked Lists without changing links of first list

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Linked lists are one of the most essential and often asked data structures in programming contests and technical interviews. There are various standard linked list problems and techniques. This blog tackles a coding task that involves In-place Merge two sorted Linked Lists without changing the links of the first list.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Problem Statement

You have been given two sorted singly linked lists, each with n and m elements, and you need to merge them utilising constant space. The first n smallest elements in both lists should go into the first list, while the rest should go into the second list. It's important to keep the sorted order. We are not permitted to alter the first linked list's pointers.

Sample Examples

Explanation

The aim is to play around with the next pointers of nodes in the two input lists and arrange them in such a way that all nodes are linked in increasing order of values.

Also read - Merge sort in linked list

In-place Merge Approach

Merge both lists and assign the first m smallest nodes to the first linked list and the remaining n nodes to the second linked list using the merge sort method, where m and n are the total number of items in the first and second linked lists, respectively. But, by changing the links in the first list, this solution violates the problem constraints. However, there is no restriction on swapping data between the linked list nodes.

The concept is to compare each node in the first list to the head node in the second list, swapping data if the current node in the first list is greater than the head node in the second list. With this data exchange, the first list's sorted order will be preserved, while the second list's sorted order may be disturbed. To solve that, use the mergeLists() function to remove the front node from the second list and place it in its proper location in the sorted second list.

Algorithm

  1. Make two pointers, let's call them ptr1 and ptr2. Find the smallest of the two nodes by comparing the first node of both lists. Assign pointer ptr1 to the node with the smaller value.
     
  2. Make a pointer to ptr1. Iterating through both lists until the value pointed by ptr1 is less than or equal to the value pointed by ptr2 is what an iteration is all about.
     
  3. Begin iterating and make a variable called temp. In an iteration, it will retain track of the last node in the sorted list. 
     
  4. When an iteration is finished, link the temp node to the ptr2 node. ptr1 and ptr2 should be swapped.
     
  5. If any of the pointers between ptr1 and ptr2 is NULL, the node referenced by temp should be moved to the next higher value node.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
};

void push(struct Node** headref, int newdata)
{
    /* allocate the node */
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));
 
    new_node->data  = newdata;
    
    new_node->next = (*headref);
 
    (*headref) = new_node;
}
 
// Function to merge two sorted linked lists
void mergeLists(struct Node *l1, struct Node * &l2)
{
    while (l1 && l2)
    {
        // compare elements in l1 with first element in l2
        if (l1->data > l2->data)
        {
            // swap the data 
            swap(l1->data, l2->data);
 
            struct Node *temp = l2;

//Place the initial element of L2 
//in its proper location to keep L2 sorted
            if (l2->next && l2->data > l2->next->data)
            {
                l2 = l2->next;
                struct Node *ptr= l2, *prev = NULL;
                while (ptr && ptr->data < temp->data)
                {
                    prev = ptr;
                    ptr = ptr -> next;
                }
 
                // update the pointers
                prev->next = temp;
                temp->next = ptr;
            }
        }
 
        // move to next element
        l1 = l1->next;
    }
}


void print(struct Node *head)
{
    while (head)
    {
        cout << head->data << "->" ;
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main()
{
    // Creating the two input linked lists.
    struct Node *a = NULL;
    push(&a, 10);
    push(&a, 8);
    push(&a, 7);
    push(&a, 4);
 
    struct Node *b = NULL;
    push(&b, 12);
    push(&b, 3);
    push(&b, 1);
 
    mergeLists(a, b);
 
    cout << "First List: ";
    print(a);
 
    cout << "Second List: ";
    print(b);
 
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Implementation in Python

# Structure for a linked list node
class Node:
     
    def __init__(self):
         
        self.data = 0
        self.next = None


def push(headref, newdata):
 
    # Allocate node
    new_node = Node()
  
    new_node.data  = newdata
  
    new_node.next = (headref)
  
    (headref) = new_node
    return headref
 
# Function to merge two sorted linked lists
def mergeLists(l1, l2):
 
    while (l1 and l2):
 
        # compare elements in a with the first element in b
        if (l1.data > l2.data):
     
            # Swap the data 
            l1.data, l2.data = l2.data, l1.data
  
            temp = l2
#Place the initial element of L2 
#in its proper location to keep L2 sorted
            if (l2.next and l2.data > l2.next.data):
                l2 = l2.next
                ptr = l2
                prev = None
                
                while (ptr and ptr.data < temp.data):
                    prev = ptr
                    ptr = ptr.next
         
                # Correct the pointers
                prev.next = temp
                temp.next = ptr
         
        # Move LL1 pointer to next element
        l1 = l1.next
     
# Function to print the linked link
def printList(head):
 
    while (head):
        print(head.data, end = '->')
        head = head.next
     
    print('NULL')
     
# Driver code
if __name__=='__main__':
     
    a = None
    a = push(a, 10)
    a = push(a, 8)
    a = push(a, 7)
    a = push(a, 4)
  
    b = None
    b = push(b, 12)
    b = push(b, 3)
    b = push(b, 1)
  
    mergeLists(a, b)
  
    print("First List: ", end = '')
    printList(a)
  
    print("Second List: ", end = '')
    printList(b)
You can also try this code with Online Python Compiler
Run Code


Output

First List: 1 -> 3 -> 4-> 7-> NULL
Second List: 8 -> 10 -> 12 -> NULL

Time Complexity

In the worst-case scenario, we traverse both lists entirely. As a result, O(N+M), where N is the number of nodes in the first list and M is the number of nodes in the second list, remains the same.

Space Complexity

We're utilising the same lists as before, but we've changed the links to make our desired list. As a result, no more room is required. As a result, its spatial complexity is O(1).

Check out this problem - Next Smaller Element

Frequently Asked Questions

Why is the space complexity of the above approach O(1)?

We're utilising the same lists as before, but we've changed the links to make our desired list. As a result, no more room is required.
 

Is merge sort in-place for linked lists?

The most typical implementation of merge sort does not sort in place; as a result, the input memory size must be allocated for the sorted output to be stored in.
 

Why do we prefer merge sort in linked lists?

Because the nodes in linked lists may not be present in adjacent memory locations, Merge Sort is employed. We can put items in the midst of linked lists in O(1) extra space and O(1) time if we are provided a reference/pointer to the previous node, unlike arrays.

Conclusion

This article extensively discussed the problem of In-place Merge two sorted Linked Lists without changing links of the first list and its time and space complexities.

We hope this blog has helped you enhance your knowledge regarding Linked Lists. Are you interested in reading/exploring additional articles about this topic? Don't worry; Coding Ninjas has you covered. See Time Complexity and AnalysisSorting Based ProblemsNumber Theory, and Dynamic Programing to learn.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive Programming, and many more! You can also check Interview Experiences and Interview Preparation Resources if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass