Insert a linked list into another linked list

0 0 10 minutes read

Given two linked lists, list1 and list2 of sizes m and n respectively. The task is to remove list1’s nodes from the a^th node to the b^th node and insert the list2 in their place.
Examples:

Input: list1: 10->11->12->13->14->15, list2: 100->101->102->103, a = 3, b = 4
Output: 10->11->12->100->101->102->103->15
Explanation: Remove the nodes from 3rd index till 4th index (0-based) from list1 and insert list2 at their place.
Input: list1: 1->2, list2: 3->4, a = 0, b = 1
Output: 3->4

Approach: The task can be solved using simple iteration over the lists. Follow the below steps to solve the problem:

Start iterating over the linked list1 until the a^th node
Now here take another variable and store the address of (a+1)^th node of the list1 and link a^th node to the list2 and then iterate over the list2 until the last node and just stop there
Iterate from (a+1)^th node to the b^th node of the list1 and then link the last node of the list2 to the (b+1) node of the list1.
Return the head node of the list1 and then print the whole list1 which will be the expected output.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
};
 
// Given a reference (pointer to pointer)
// to the head of a list and an int,
// appends a new node at the end
void append(Node** head_ref, int new_data)
{
    /* 1. allocate node */
    Node* new_node = new Node();
 
    Node* last = *head_ref; /* used in step 5*/
 
    /* 2. put in the data */
    new_node->data = new_data;
 
    /* 3. This new node is going to be
    the last node, so make next of
    it as NULL*/
    new_node->next = NULL;
 
    /* 4. If the Linked List is empty,
    then make the new node as head */
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
 
    /* 5. Else traverse till the last node */
    while (last->next != NULL) {
        last = last->next;
    }
 
    /* 6. Change the next of last node */
    last->next = new_node;
    return;
}
 
/* Given a reference (pointer to pointer)
 to the head of a list */
void mergeInBetween(Node** list1, Node** list2,
                    int a, int b)
{
    // keeping the index count
    int cnt = 0;
 
    // taking a new variable for
    // iterating over the linked list1
    Node* list = *list1;
    // condition for checking
    // till the count reached index a
    while (cnt + 1 != a) {
        // pointing the next node
        list = list->next;
        // increasing the count value everytime
        cnt++;
    }
    // Now demo will be used
    // to iterate from (a+1)th node
    // of list1 to bth node of list1
    Node* demo = list->next;
    // now we are linking
    // the ath node to the list2
    list->next = *list2;
    // now we use samp
    // for iterating over the list2
    Node* samp = *list2;
    // we go until the last node of the list2
    while (samp->next != NULL)
        samp = samp->next;
    // we go until the bth node of the list1
    while (cnt + 1 != b) {
        demo = demo->next;
        cnt++;
    }
    // now we simply link disconnected
    // parts of list1 and list2
    demo = demo->next;
    samp->next = demo;
}
 
// This function prints contents of
// linked list starting from head
void printList(Node* node)
{
    while (node != NULL) {
        cout << " " << node->data;
        node = node->next;
    }
}
 
/* Driver code*/
int main()
{
    Node *list1 = NULL, *list2 = NULL;
    append(&list1, 10);
    append(&list1, 11);
    append(&list1, 12);
    append(&list1, 13);
    append(&list1, 14);
    append(&list1, 15);
    append(&list2, 100);
    append(&list2, 101);
    append(&list2, 102);
    append(&list2, 103);
    int a = 3, b = 4;
    mergeInBetween(&list1, &list2, a, b);
    printList(list1);
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG{
 
static class Node {
    int data;
    Node next;
};
 
    // Given a reference (pointer to pointer)
    // to the head of a list and an int,
    // appends a new node at the end
static Node append(Node head_ref, int new_data)
{
    /* 1. allocate node */
    Node new_node = new Node();
 
    Node last = head_ref; /* used in step 5*/
 
    /* 2. put in the data */
    new_node.data = new_data;
 
    /* 3. This new node is going to be
    the last node, so make next of
    it as null*/
    new_node.next = null;
 
    /* 4. If the Linked List is empty,
    then make the new node as head */
    if (head_ref == null) {
        head_ref = new_node;
        return head_ref;
    }
 
    /* 5. Else traverse till the last node */
    while (last.next != null) {
        last = last.next;
    }
 
    /* 6. Change the next of last node */
    last.next = new_node;
    return head_ref;
}
 
    /*
     * Given a reference (pointer to pointer) to the head of a list
     */
static Node mergeInBetween(Node list1, Node list2,
                    int a, int b)
{
    // keeping the index count
    int cnt = 0;
 
    // taking a new variable for
    // iterating over the linked list1
    Node list = list1;
    // condition for checking
    // till the count reached index a
    while (cnt + 1 != a) {
        // pointing the next node
        list = list.next;
        // increasing the count value everytime
        cnt++;
    }
    // Now demo will be used
    // to iterate from (a+1)th node
    // of list1 to bth node of list1
    Node demo = list.next;
    // now we are linking
    // the ath node to the list2
    list.next = list2;
    // now we use samp
    // for iterating over the list2
    Node samp = list2;
    // we go until the last node of the list2
    while (samp.next != null)
        samp = samp.next;
    // we go until the bth node of the list1
    while (cnt + 1 != b) {
        demo = demo.next;
        cnt++;
    }
    // now we simply link disconnected
    // parts of list1 and list2
    demo = demo.next;
    samp.next = demo;
    return list1;
}
 
    // This function prints contents of
    // linked list starting from head
static void printList(Node node)
{
    while (node != null) {
        System.out.print(" " +  node.data);
        node = node.next;
    }
}
 
    /* Driver code */
public static void main(String[] args)
{
    Node list1 = null, list2 = null;
    list1= append(list1, 10);
    list1 = append(list1, 11);
    list1= append(list1, 12);
    list1 = append(list1, 13);
    list1 =append(list1, 14);
    list1 = append(list1, 15);
    list2 = append(list2, 100);
    list2 = append(list2, 101);
    list2 = append(list2, 102);
    list2 =append(list2, 103);
    int a = 3, b = 4;
    list1  = mergeInBetween(list1, list2, a, b);
    printList(list1);
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python implementation of the above approach
class Node:
    def __init__(self):
        self.data = 0; 
        self.next = None;
 
# Given a reference (pointer to pointer)
# to the head of a list and an int,
# appends a new Node at the end
def append(head_ref, new_data):
   
    ''' 1. allocate Node '''
    new_Node = Node();
 
    last = head_ref; ''' used in step 5 '''
 
    ''' 2. put in the data '''
    new_Node.data = new_data;
 
    '''
     * 3. This new Node is going to be the last Node, so make next of it as None
     '''
    new_Node.next = None;
 
    '''
     * 4. If the Linked List is empty, then make the new Node as head
     '''
    if (head_ref == None):
        head_ref = new_Node;
        return head_ref;
 
    ''' 5. Else traverse till the last Node '''
    while (last.next != None):
        last = last.next;
     
    ''' 6. Change the next of last Node '''
    last.next = new_Node;
    return head_ref;
 
'''
 * Given a reference (pointer to pointer) to the head of a list
 '''
def mergeInBetween(list1, list2, a, b):
   
    # keeping the index count
    cnt = 0;
 
    # taking a new variable for
    # iterating over the linked list1
    list = list1;
     
    # condition for checking
    # till the count reached index a
    while (cnt + 1 != a):
       
        # pointing the next Node
        list = list.next;
         
        # increasing the count value everytime
        cnt += 1;
     
    # Now demo will be used
    # to iterate from (a+1)th Node
    # of list1 to bth Node of list1
    demo = list.next;
     
    # now we are linking
    # the ath Node to the list2
    list.next = list2;
     
    # now we use samp
    # for iterating over the list2
    samp = list2;
     
    # we go until the last Node of the list2
    while (samp.next != None):
        samp = samp.next;
         
    # we go until the bth Node of the list1
    while (cnt + 1 != b):
        demo = demo.next;
        cnt+=1;
     
    # now we simply link disconnected
    # parts of list1 and list2
    demo = demo.next;
    samp.next = demo;
    return list1;
 
# This function prints contents of
# linked list starting from head
def printList(Node):
    while (Node != None):
        print(Node.data, end=" ");
        Node = Node.next;
 
''' Driver code '''
if __name__ == '__main__':
    list1 = None;
    list2 = None;
    list1 = append(list1, 10);
    list1 = append(list1, 11);
    list1 = append(list1, 12);
    list1 = append(list1, 13);
    list1 = append(list1, 14);
    list1 = append(list1, 15);
    list2 = append(list2, 100);
    list2 = append(list2, 101);
    list2 = append(list2, 102);
    list2 = append(list2, 103);
    a = 3
    b = 4;
    list1 = mergeInBetween(list1, list2, a, b);
    printList(list1);
 
# This code is contributed by gauravrajput1

C#

// C# implementation of the above approach
using System;
 
public class GFG{
 
  class Node {
    public int data;
    public Node next;
  };
 
  // Given a reference (pointer to pointer)
  // to the head of a list and an int,
  // appends a new node at the end
  static Node append(Node head_ref, int new_data)
  {
 
    /* 1. allocate node */
    Node new_node = new Node();
 
    Node last = head_ref; /* used in step 5*/
 
    /* 2. put in the data */
    new_node.data = new_data;
 
    /* 3. This new node is going to be
    the last node, so make next of
    it as null*/
    new_node.next = null;
 
    /* 4. If the Linked List is empty,
    then make the new node as head */
    if (head_ref == null) {
      head_ref = new_node;
      return head_ref;
    }
 
    /* 5. Else traverse till the last node */
    while (last.next != null) {
      last = last.next;
    }
 
    /* 6. Change the next of last node */
    last.next = new_node;
    return head_ref;
  }
 
  /*
     * Given a reference (pointer to pointer) to the head of a list
     */
  static Node mergeInBetween(Node list1, Node list2,
                             int a, int b)
  {
 
    // keeping the index count
    int cnt = 0;
 
    // taking a new variable for
    // iterating over the linked list1
    Node list = list1;
    // condition for checking
    // till the count reached index a
    while (cnt + 1 != a)
    {
 
      // pointing the next node
      list = list.next;
 
      // increasing the count value everytime
      cnt++;
    }
 
    // Now demo will be used
    // to iterate from (a+1)th node
    // of list1 to bth node of list1
    Node demo = list.next;
 
    // now we are linking
    // the ath node to the list2
    list.next = list2;
 
    // now we use samp
    // for iterating over the list2
    Node samp = list2;
 
    // we go until the last node of the list2
    while (samp.next != null)
      samp = samp.next;
 
    // we go until the bth node of the list1
    while (cnt + 1 != b) {
      demo = demo.next;
      cnt++;
    }
 
    // now we simply link disconnected
    // parts of list1 and list2
    demo = demo.next;
    samp.next = demo;
    return list1;
  }
 
  // This function prints contents of
  // linked list starting from head
  static void printList(Node node)
  {
    while (node != null) {
      Console.Write(" " +  node.data);
      node = node.next;
    }
  }
 
  /* Driver code */
  public static void Main(String[] args)
  {
    Node list1 = null, list2 = null;
    list1= append(list1, 10);
    list1 = append(list1, 11);
    list1= append(list1, 12);
    list1 = append(list1, 13);
    list1 = append(list1, 14);
    list1 = append(list1, 15);
    list2 = append(list2, 100);
    list2 = append(list2, 101);
    list2 = append(list2, 102);
    list2 = append(list2, 103);
    int a = 3, b = 4;
    list1  = mergeInBetween(list1, list2, a, b);
    printList(list1);
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript implementation of the above approach
 
 class Node {
     
    constructor(){
    this.data = 0;
    this.next = null;
    }
}
 
    // Given a reference (pointer to pointer)
    // to the head of a list and an int,
    // appends a new node at the end
function append(head_ref , new_data)
{
    /* 1. allocate node */
    var new_node = new Node();
 
    var last = head_ref; /* used in step 5*/
 
    /* 2. put in the data */
    new_node.data = new_data;
 
    /* 3. This new node is going to be
    the last node, so make next of
    it as null*/
    new_node.next = null;
 
    /* 4. If the Linked List is empty,
    then make the new node as head */
    if (head_ref == null) {
        head_ref = new_node;
        return head_ref;
    }
 
    /* 5. Else traverse till the last node */
    while (last.next != null) {
        last = last.next;
    }
 
    /* 6. Change the next of last node */
    last.next = new_node;
    return head_ref;
}
 
    /*
     * Given a reference (pointer to pointer) to the head of a list
     */
function mergeInBetween(list1,  list2,
                     a , b){
    // keeping the index count
    var cnt = 0;
 
    // taking a new variable for
    // iterating over the linked list1
    var list = list1;
    // condition for checking
    // till the count reached index a
    while (cnt + 1 != a) {
        // pointing the next node
        list = list.next;
        // increasing the count value everytime
        cnt++;
    }
    // Now demo will be used
    // to iterate from (a+1)th node
    // of list1 to bth node of list1
    var demo = list.next;
     
    // now we are linking
    // the ath node to the list2
    list.next = list2;
     
    // now we use samp
    // for iterating over the list2
    var samp = list2;
     
    // we go until the last node of the list2
    while (samp.next != null)
        samp = samp.next;
         
    // we go until the bth node of the list1
    while (cnt + 1 != b) {
        demo = demo.next;
        cnt++;
    }
     
    // now we simply link disconnected
    // parts of list1 and list2
    demo = demo.next;
    samp.next = demo;
    return list1;
}
 
    // This function prints contents of
    // linked list starting from head
function printList(node)
{
    while (node != null) {
        document.write(" " +  node.data);
        node = node.next;
    }
}
 
    /* Driver code */
    var list1 = null, list2 = null;
    list1= append(list1, 10);
    list1 = append(list1, 11);
    list1= append(list1, 12);
    list1 = append(list1, 13);
    list1 =append(list1, 14);
    list1 = append(list1, 15);
    list2 = append(list2, 100);
    list2 = append(list2, 101);
    list2 = append(list2, 102);
    list2 =append(list2, 103);
    var a = 3, b = 4;
    list1  = mergeInBetween(list1, list2, a, b);
    printList(list1);
 
// This code is contributed by gauravrajput1
</script>

Output:

10 11 12 100 101 102 103 15

Time Complexity: O(m+n), n is the length of list1 and m is the length of list2
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!