Given two linked lists and a number k. Insert second linked list in to first at k-th position
Examples:
Input : a : 1->2->3->4->5->NULL
b : 7->8->9->10->11->NULL
k = 2
Output :1->2->7->8->9->10->11->3->4->5->NULL
Input : a: 10->15->20->NULL
b: 11->17->16->18->NULL
k = 3
Output : 10->15->20->11->17->16->18->NULL
A pictorial representation of the problem
- Traverse the first linked list till k-th point
- Join second linked list head node to k-th point of first linked list
- Traverse the second linked list till end at
- Add (k+1)th point of first linked list to the end of the second linked list
Implementation:
C++
// A C++ program to insert a linked list in// to another linked list at position k#include <bits/stdc++.h>using namespace std;/* Structure for a linked list node */struct Node { int data; struct Node* next;};// Function to insert whole linked list in// to another linked list at position kvoid insert(struct Node* head1, struct Node* head2, int k){ // traverse the first linked list until k-th // point is reached int count = 1; struct Node* curr = head1; while (count < k) { curr = curr->next; count++; } // backup next node of the k-th point struct Node* temp = curr->next; // join second linked list at the kth point curr->next = head2; // traverse the second linked list till end while (head2->next != NULL) head2 = head2->next; // join the second part of the linked list // to the end head2->next = temp;}// Function to print linked list recursivelyvoid printList(Node* head){ if (head == NULL) return; // If head is not NULL, print current node // and recur for remaining list cout << head->data << " "; printList(head->next);}/* Given a reference (pointer to pointer) to the head of a list and an int, insert a new node on the front of the list. */void push(struct Node** head_ref, int new_data){ struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}/* Driven program to test above function */int main(){ /* The constructed linked lists are : a: 1->2->3->4->5; b: 7->8->9->10->11 */ struct Node* a = NULL; struct Node* b = NULL; int k = 2; // first linked list push(&a, 5); push(&a, 4); push(&a, 3); push(&a, 2); push(&a, 1); // second linked list push(&b, 11); push(&b, 10); push(&b, 9); push(&b, 8); push(&b, 7); printList(a); cout << "\n"; printList(b); insert(a, b, k); cout << "\nResulting linked list\t"; printList(a); return 0;} |
Java
// A Java program to insert a linked list in// to another linked list at position kclass GFG { // Structure for a linked list node / static class Node { int data; Node next; }; // Function to insert whole linked list in // to another linked list at position k static Node insert(Node head1, Node head2, int k) { // traverse the first linked list until k-th // point is reached int count = 1; Node curr = head1; while (count < k) { curr = curr.next; count++; } // backup next node of the k-th point Node temp = curr.next; // join second linked list at the kth point curr.next = head2; // traverse the second linked list till end while (head2.next != null) head2 = head2.next; // join the second part of the linked list // to the end head2.next = temp; return head1; } // Function to print linked list recursively static void printList(Node head) { if (head == null) return; // If head is not null, print current node // and recur for remaining list System.out.print(head.data + " "); printList(head.next); } // Given a reference (pointer to pointer) to the head // of a list and an int, insert a new node on the front // of the list. static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Driven code public static void main(String args[]) { // The constructed linked lists are : // a: 1.2.3.4.5; // b: 7.8.9.10.11 Node a = null; Node b = null; int k = 2; // first linked list a = push(a, 5); a = push(a, 4); a = push(a, 3); a = push(a, 2); a = push(a, 1); // second linked list b = push(b, 11); b = push(b, 10); b = push(b, 9); b = push(b, 8); b = push(b, 7); printList(a); System.out.println(); printList(b); a = insert(a, b, k); System.out.print("\nResulting linked list\t"); printList(a); }}// This code is contributed by Arnab Kundu |
Python3
# A Python3 program to insert a linked list in# to another linked list at position k# Node of the single linked list class Node: def __init__(self, data): self.data = data self.next = None# Function to insert whole linked list in# to another linked list at position kdef insert(head1, head2, k): # traverse the first linked list until k-th # point is reached count = 1 curr = head1 while (count < k): curr = curr.next count += 1 # backup next node of the k-th point temp = curr.next # join second linked list at the kth point curr.next = head2 # traverse the second linked list till end while (head2.next != None): head2 = head2.next # join the second part of the linked list # to the end head2.next = temp return head1# Function to print linked list recursivelydef printList(head): if (head == None): return # If head is not None, print current node # and recur for remaining list print( head.data, end = " ") printList(head.next)""" Given a reference (pointer to pointer) to the headof a list and an int, insert a new node on the frontof the list. """def push(head_ref, new_data): new_node = Node(0) new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref# Driver Codeif __name__ == "__main__": """ The constructed linked lists are : a: 1.2.3.4.5 b: 7.8.9.10.11 """ a = None b = None k = 2 # first linked list a = push(a, 5) a = push(a, 4) a = push(a, 3) a = push(a, 2) a = push(a, 1) # second linked list b = push(b, 11) b = push(b, 10) b = push(b, 9) b = push(b, 8) b = push(b, 7) printList(a) print() printList(b) a = insert(a, b, k) print("\nResulting linked list\t", end = " "); printList(a)# This code is contributed by Arnab Kundu |
C#
// A C# program to insert a linked list in// to another linked list at position kusing System;class GFG { // Structure for a linked list node / public class Node { public int data; public Node next; }; // Function to insert whole linked list in // to another linked list at position k static Node insert(Node head1, Node head2, int k) { // traverse the first linked list until k-th // point is reached int count = 1; Node curr = head1; while (count < k) { curr = curr.next; count++; } // backup next node of the k-th point Node temp = curr.next; // join second linked list at the kth point curr.next = head2; // traverse the second linked list till end while (head2.next != null) head2 = head2.next; // join the second part of the linked list // to the end head2.next = temp; return head1; } // Function to print linked list recursively static void printList(Node head) { if (head == null) return; // If head is not null, print current node // and recur for remaining list Console.Write(head.data + " "); printList(head.next); } // Given a reference (pointer to pointer) to the head // of a list and an int, insert a new node on the front // of the list. static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Driven code public static void Main(String[] args) { // The constructed linked lists are : // a: 1.2.3.4.5; // b: 7.8.9.10.11 Node a = null; Node b = null; int k = 2; // first linked list a = push(a, 5); a = push(a, 4); a = push(a, 3); a = push(a, 2); a = push(a, 1); // second linked list b = push(b, 11); b = push(b, 10); b = push(b, 9); b = push(b, 8); b = push(b, 7); printList(a); Console.WriteLine(); printList(b); a = insert(a, b, k); Console.Write("\nResulting linked list\t"); printList(a); }}// This code contributed by Rajput-Ji |
Javascript
<script>// A Javascript program to insert a linked list in// to another linked list at position k// Structure for a linked list node /class Node { constructor() { this.data = 0; this.next = null; }};// Function to insert whole linked list in// to another linked list at position kfunction insert(head1, head2, k){ // traverse the first linked list until k-th // point is reached var count = 1; var curr = head1; while (count < k) { curr = curr.next; count++; } // backup next node of the k-th point var temp = curr.next; // join second linked list at the kth point curr.next = head2; // traverse the second linked list till end while (head2.next != null) head2 = head2.next; // join the second part of the linked list // to the end head2.next = temp; return head1;}// Function to print linked list recursivelyfunction printList(head){ if (head == null) return; // If head is not null, print current node // and recur for remaining list document.write(head.data + " "); printList(head.next);}// Given a reference (pointer to pointer) to the head// of a list and an int, insert a new node on the front// of the list.function push(head_ref, new_data){ var new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref;}// Driven code// The constructed linked lists are :// a: 1.2.3.4.5;// b: 7.8.9.10.11var a = null;var b = null;var k = 2;// first linked lista = push(a, 5);a = push(a, 4);a = push(a, 3);a = push(a, 2);a = push(a, 1);// second linked listb = push(b, 11);b = push(b, 10);b = push(b, 9);b = push(b, 8);b = push(b, 7);printList(a);document.write("<br>");printList(b);a = insert(a, b, k);document.write("<br>Resulting linked list ");printList(a);</script> |
Output:
1 2 3 4 5 7 8 9 10 11 Resulting linked list 1 2 7 8 9 10 11 3 4 5
Time Complexity: O(k+n), as we are using a loop to traverse second linked list n times. Where n is the number of nodes in the second linked list to be inserted. and kth position in first linked list
Auxiliary Space: O(1) because it is using constant space
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!
