Given two linked lists, list1 and list2 of sizes m and n respectively. The task is to remove list1’s nodes from the ath node to the bth 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 ath node
- Now here take another variable and store the address of (a+1)th node of the list1 and link ath 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 bth 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 endvoid 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 headvoid 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 approachimport 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 endstatic 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 headstatic 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 approachclass 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 enddef 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 headdef 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 approachusing 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 endfunction 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 headfunction 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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
