Insert a whole linked list into other at k-th position

0 0 8 minutes read

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 k
void 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 recursively
void 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 k
class 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 k
def 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 recursively
def 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 head
of a list and an int, insert a new node on the front
of 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 Code
if __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 k
using 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 k
function 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 recursively
function 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.11
var a = null;
var b = null;
var 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);
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

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!