How to insert a Node in a Singly Linked List at a given Position using Recursion

0 0 12 minutes read

Given a singly linked list as list, a position, and a node, the task is to insert that element in the given linked list at a given position using recursion.

Examples:

Input: list = 1->2->3->4->5->6->7, node = (val=100,next=null), position = 4
Output: 1->2->3->100->4->5->6->7
Explanation: Here the node with value 100 is being inserted at the 4th position. Initially at the 4th position the value is 4. Now when 100 is inserted at 4th position all the value starting from 4 will shift 1 position to its right. This can be visualised in the following way:

1->2->3->4->5->6->7
1->2->3->100->4->5->6->7

Input: list = 1->2->3->100->4->5->6->7, node = (val=101,next=null), position = 1
Output: 10->1->2->3->100->4->5->6->7

Solution:

There will be 3 cases:

Insert a node at first position of linked list
- Approach: Follow the steps mentioned below:
  1. Create a temporary node.
  2. Now insert the temporary node before head and change the head pointer to point the temporary node.
Insert a node in between first and last node of linked list
- Approach: Follow the steps mentioned below:
  1. Call the recursive function to reach to the desired position.
  2. If the position is greater than the length of the list then insertion is not possible.
  3. If not, then insert the new node at the desired position.
Insert a node at the end of linked list
- Approach: Follow the steps mentioned below:
  1. Recursively move to the end of the linked list.
  2. Insert the new node at the end of the list.

Recurrence relation: T(n) = T(n-1) + c

Below is the implementation of above approach

C++

// C++ code to insert a node
// at a given position
// in singly linked list
#include <bits/stdc++.h>
#define null nullptr
 
using namespace std;
 
// Structure of the node of linked list
struct node {
    int item;
    node* nxt;
    node(int item, node* t)
    {
        this->item = item;
        (*this).nxt = t;
    }
};
 
// Function to insert a node
// at the first position
node* insertAtFirst(node*& listHead, node* x)
{
    node* temp = listHead;
    x->nxt = temp;
    listHead = temp = x;
    return temp;
}
 
// Function to insert a node
// at the last position
node* insertAtEnd(node* listHead, node* x)
{
    if (listHead->nxt == null) {
        listHead->nxt = x;
        return listHead;
    }
    listHead->nxt 
      = insertAtEnd(listHead->nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
node* insertInBetween(node* temp, 
                      node* x, int pos)
{
    if (pos == 2) {
        if (temp != null) {
            x->nxt = temp->nxt;
            temp->nxt = x;
        }
        return temp;
    }
    if (temp == null) {
        return temp;
    }
    temp->nxt 
      = insertInBetween(temp->nxt, x, --pos);
}
 
// Printing through recursion
void print(node* head)
{
    if (head == null) {
        return;
    }
    cout << head->item << " ";
    print(head->nxt);
}
 
// Driver code
int main()
{
    node* head = new node(1, 0);
 
    // Creating a linked list of length 15
    for (int i = 2; i < 16; i++)
        insertAtEnd(head, new node(i, 0));
 
    // Insert node with value 100 
    // at 4th position
    insertInBetween(head, 
                    new node(100, 0), 4);
 
    // Insert node with value 101 
    // at 200th position
    insertInBetween(head, 
                    new node(101, 0), 200);
 
    // Insert node with value 100 
    // at 1st position
    insertAtFirst(head, new node(100, 0));
 
    // Insert node with value 100 
    // at the end position
    insertAtEnd(head, new node(100, 0));
 
    // Printing the new linked list
    print(head);
    return 0;
}

Java

// Java code to insert a node at a given
//position in singly linked list
class GFG{
 
// Structure of the node of linked list
static class node
{
    int item;
    node nxt;
     
    node(int item, node t)
    {
        this.item = item;
        this.nxt = t;
    }
};
 
// Function to insert a node
// at the first position
static node insertAtFirst(node listHead, node x)
{
    x.nxt = listHead;
    listHead = null;
    listHead = x;
    return listHead;
}
 
// Function to insert a node
// at the last position
static node insertAtEnd(node listHead, node x)
{
    if (listHead.nxt == null)
    {
        listHead.nxt = x;
        return listHead;
    }
    listHead.nxt = insertAtEnd(listHead.nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
static node insertInBetween(node temp, node x, 
                            int pos)
{
    if (pos == 2)
    {
        if (temp != null) 
        {
            x.nxt = temp.nxt;
            temp.nxt = x;
        }
        return temp;
    }
    if (temp == null) 
    {
        return temp;
    }
    temp.nxt = insertInBetween(temp.nxt, x, --pos);
    return temp;
}
 
// Printing through recursion
static void print(node head)
{
    if (head == null) 
    {
        return;
    }
    System.out.print(head.item + " ");
    print(head.nxt);
}
 
// Driver code
public static void main(String[] args)
{
    node head = new node(1, null);
 
    // Creating a linked list of length 15
    for(int i = 2; i < 16; i++)
        insertAtEnd(head, new node(i, null));
 
    // Insert node with value 100 
    // at 4th position
    head = insertInBetween(head, 
                    new node(100, null), 4);
 
    // Insert node with value 101 
    // at 200th position
    head = insertInBetween(head, 
                    new node(101, null), 200);
 
    // Insert node with value 100 
    // at 1st position
    head = insertAtFirst(head, new node(100, null));
 
    // Insert node with value 100 
    // at the end position
    head = insertAtEnd(head, new node(100, null));
 
    // Printing the new linked list
    print(head);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python code to insert a node in a
# given Singly Linked List (recursively)
 
class Node:
 
    # Structure of the node.
    def __init__(self, item):
        self.item = item
        self.nxt = None
     
 
# Function to insert a node at 
# first position in the given 
# Linked List
def insertAtFirst(listHead, item):
    new = Node(item)
    new.nxt = listHead
    return new
# Time Complexity - O(1)
 
 
# Function to insert a node 
# at the end of the given 
# Linked List (recursively)
def insertAtEnd(listHead, item):
    if listHead is None:
        new = Node(item)
        return new
 
    if listHead.nxt is None:
        new = Node(item)
        listHead.nxt = new
        return listHead
     
    insertAtEnd(listHead.nxt, item)
    return listHead
# Time Complexity - O(n)
 
 
# Function to insert a node 
# at a specific position in
# the given Linked List (recursively)
def insertInBetween(temp, item, pos):
 
    # if head is None and given position is greater than 0
    if temp is None and pos>0:
        return temp
 
    # if the node is to be added at first position
    if pos==0:
        new = Node(item)
        new.nxt = temp
        return new
     
    # if the node is to be added at second position
    if pos==1:
        new = Node(item)
        new.nxt = temp.nxt
        temp.nxt = new
        return temp
    insertInBetween(temp.nxt, item, pos-1)
    return temp
# Time Complexity - O(i)
 
 
# Function to print the Linked List through Recursion
def printll(head):
    if head==None:
        return
    print(head.item, end=' ')
    printll(head.nxt)
# Time Complexity - O(n)
# where n is the length of the linked list
 
 
# Driver code
if __name__=='__main__':
     
    head = None
 
    # Creating a Linked List of length 15
    for i in range(1, 16):
        head = insertAtEnd(head, i)
     
    # Insert node with value 100
    # at 4th position
    head = insertInBetween(head, 100, 3)
 
    # Insert node with value 101
    # at 200th position
    head = insertInBetween(head, 101, 200)
 
    # Insert node with value 100
    # at 1st position
    head = insertAtFirst(head, 100)
 
    # Insert node with value 100
    # at the end position
    head = insertAtEnd(head, 100)
 
    # Printing the new linked list
    printll(head)
 
# This code is contributed by Harshit Rathore

C#

// C# code to insert a node at a given
//position in singly linked list
using System;
 
public class GFG{
 
// Structure of the node of linked list
class node
{
    public int item;
    public node nxt;
     
    public node(int item, node t)
    {
        this.item = item;
        this.nxt = t;
    }
};
 
// Function to insert a node
// at the first position
static node insertAtFirst(node listHead, node x)
{
    x.nxt = listHead;
    listHead = null;
    listHead = x;
    return listHead;
}
 
// Function to insert a node
// at the last position
static node insertAtEnd(node listHead, node x)
{
    if (listHead.nxt == null)
    {
        listHead.nxt = x;
        return listHead;
    }
    listHead.nxt = insertAtEnd(listHead.nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
static node insertInBetween(node temp, node x, 
                            int pos)
{
    if (pos == 2)
    {
        if (temp != null) 
        {
            x.nxt = temp.nxt;
            temp.nxt = x;
        }
        return temp;
    }
    if (temp == null) 
    {
        return temp;
    }
    temp.nxt = insertInBetween(temp.nxt, x, --pos);
    return temp;
}
 
// Printing through recursion
static void print(node head)
{
    if (head == null) 
    {
        return;
    }
    Console.Write(head.item + " ");
    print(head.nxt);
}
 
// Driver code
public static void Main(String[] args)
{
    node head = new node(1, null);
 
    // Creating a linked list of length 15
    for(int i = 2; i < 16; i++)
        insertAtEnd(head, new node(i, null));
 
    // Insert node with value 100 
    // at 4th position
    head = insertInBetween(head, 
                    new node(100, null), 4);
 
    // Insert node with value 101 
    // at 200th position
    head = insertInBetween(head, 
                    new node(101, null), 200);
 
    // Insert node with value 100 
    // at 1st position
    head = insertAtFirst(head, new node(100, null));
 
    // Insert node with value 100 
    // at the end position
    head = insertAtEnd(head, new node(100, null));
 
    // Printing the new linked list
    print(head);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// Javascript code to insert a node at a given
// position in singly linked list
 
// Structure of the node of linked list
class node {
 
    constructor(item, t) {
        this.item = item;
        this.nxt = t;
    }
};
 
// Function to insert a node
// at the first position
function insertAtFirst(listHead, x) {
    x.nxt = listHead;
    listHead = null;
    listHead = x;
    return listHead;
}
 
// Function to insert a node
// at the last position
function insertAtEnd(listHead, x) {
    if (listHead.nxt == null) {
        listHead.nxt = x;
        return listHead;
    }
    listHead.nxt = insertAtEnd(listHead.nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
function insertInBetween(temp, x, pos) {
    if (pos == 2) {
        if (temp != null) {
            x.nxt = temp.nxt;
            temp.nxt = x;
        }
        return temp;
    }
    if (temp == null) {
        return temp;
    }
    temp.nxt = insertInBetween(temp.nxt, x, --pos);
    return temp;
}
 
// Printing through recursion
function _print(head) {
    if (head == null) {
        return;
    }
    document.write(head.item + " ");
    _print(head.nxt);
}
 
// Driver code
let head = new node(1, null);
 
// Creating a linked list of length 15
for (let i = 2; i < 16; i++)
    insertAtEnd(head, new node(i, null));
 
// Insert node with value 100 
// at 4th position
head = insertInBetween(head,
    new node(100, null), 4);
 
// Insert node with value 101 
// at 200th position
head = insertInBetween(head,
    new node(101, null), 200);
 
// Insert node with value 100 
// at 1st position
head = insertAtFirst(head, new node(100, null));
 
// Insert node with value 100 
// at the end position
head = insertAtEnd(head, new node(100, null));
 
// Printing the new linked list
_print(head);
 
    // This code is contributed by Saurabh Jaiswal
</script>

Output

100 1 100

Time Complexity: O(N) where N is the size of linked list
Auxiliary Space: O(N) where N is the size of linked list

A simpler approach of the above C++ code:

C++

#include <iostream>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
 
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};
 
Node* insertatk(Node* head, int k, int data)
{
    if (head == NULL)
        return new Node(data);
 
    if (k == 1) {
        Node* newnode = new Node(data);
        newnode->next = head;
        head = newnode;
        return head;
    }
    else
        head->next
            = insertatk(head->next, k - 1,
                        data); // we do k-1 so as to reach
                               // the required place
 
    return head;
}
 
void print(Node* head)
{
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << "\n";
}
 
int main()
{
    // inserting nodes and connecting them at the same time
    Node* head = new Node(1);
    Node* n1 = new Node(2);
    head->next = n1;
    Node* n2 = new Node(3);
    n1->next = n2;
    Node* n3 = new Node(4);
    n2->next = n3;
    Node* n4 = new Node(5);
    n3->next = n4;
    Node* n5 = new Node(6);
    n4->next = n5;
    Node* n6 = new Node(7);
    n5->next = n6;
    n6->next = NULL;
 
    int k = 4;
    int data = 100;
 
    print(insertatk(head, k, data));
    return 0;
}

Java

// Java code
 
import java.io.*;
 
public class GFG {
 
    static class Node {
        int data;
        Node next;
        public Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    }
 
    static Node insertatk(Node head, int k, int data)
    {
        if (head == null) {
            return new Node(data);
        }
        if (k == 1) {
            Node newnode = new Node(data);
            newnode.next = head;
            head = newnode;
            return head;
        }
        else {
            // we do k-1 so as to reach the required place
            head.next = insertatk(head.next, k - 1, data);
        }
        return head;
    }
 
    static void print(Node head)
    {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
 
    public static void main(String[] args)
    {
 
        // inserting nodes and connecting them at the same
        // time
        Node head = new Node(1);
        Node n1 = new Node(2);
        head.next = n1;
        Node n2 = new Node(3);
        n1.next = n2;
        Node n3 = new Node(4);
        n2.next = n3;
        Node n4 = new Node(5);
        n3.next = n4;
        Node n5 = new Node(6);
        n4.next = n5;
        Node n6 = new Node(7);
        n5.next = n6;
        n6.next = null;
 
        int k = 4;
        int data = 100;
 
        print(insertatk(head, k, data));
    }
}
 
// This code is contributed by lokeshmvs21.

Python3

# python program for the above approach
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
def insertatk(head, k, data):
    if(head is None):
        return Node(data)
 
    if(k == 1):
        newnode = Node(data)
        newnode.next = head
        head = newnode
        return head
    else:
        # we do k-1 so as to reach the required place
        head.next = insertatk(head.next, k-1, data)
    return head
 
 
def printList(head):
    temp = head
    while(temp is not None):
        print(temp.data, end=" ")
        temp = temp.next
 
 
# driver code
head = Node(1)
n1 = Node(2)
head.next = n1
n2 = Node(3)
n1.next = n2
n3 = Node(4)
n2.next = n3
n4 = Node(5)
n3.next = n4
n5 = Node(6)
n4.next = n5
n6 = Node(7)
n5.next = n6
n6.next = None
 
k = 4
data = 100
 
printList(insertatk(head, k, data))
# this code is contributed by Kirti Agarwal

C#

// C# code to insert a node at a given
// position in singly linked list
using System;
 
public class GFG {
    // Structure of the node of linked list
    public class Node {
        public int data;
        public Node next;
        public Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    };
 
    static Node insertatk(Node head, int k, int data)
    {
        if (head == null)
            return new Node(data);
        if (k == 1) {
            Node newnode = new Node(data);
            newnode.next = head;
            head = newnode;
            return head;
        }
        // we do k-1 so as to reach
        // the required place
        else
            head.next = insertatk(head.next, k - 1, data);
 
        return head;
    }
 
    // Printing through recursion
    static void print(Node head)
    {
        Node temp = head;
        while (temp != null) {
            Console.Write(temp.data + " ");
            temp = temp.next;
        }
        Console.WriteLine(" ");
    }
 
    // Driver code to test above functions
    public static void Main(String[] args)
    {
        Node head = new Node(1);
        Node n1 = new Node(2);
        head.next = n1;
        Node n2 = new Node(3);
        n1.next = n2;
        Node n3 = new Node(4);
        n2.next = n3;
        Node n4 = new Node(5);
        n3.next = n4;
        Node n5 = new Node(6);
        n4.next = n5;
        Node n6 = new Node(7);
        n5.next = n6;
        n6.next = null;
 
        int k = 4;
        int data = 100;
 
        print(insertatk(head, k, data));
    }
}
 
// THIS CODE IS CONTRIBUTED BY KIRTI
// AGARWAL(KIRTIAGARWAL23121999)

Javascript

// JavaScript Program for the above approach
class Node{
    constructor(data){
        this.data = data;
        this.next = null;
    }
}
 
function insertatk(head, k, data){
    if(head == null) return new Node(data);
     
    if(k == 1){
        let newnode = new Node(data);
        newnode.next = head;
        head = newnode;
        return head;
    }
    else{
        // we do k-1 so as to reach the required place
        head.next = insertatk(head.next, k-1, data); 
    }
    return head;
}
 
function print(head){
    let temp = head;
    while(temp != null){
        document.write(temp.data + " ");
        temp = temp.next;
    }
}
 
// Driver code
let head = new Node(1);
let n1 = new Node(2);
head.next = n1;
let n2 = new Node(3);
n1.next = n2;
let n3 = new Node(4);
n2.next = n3;
let n4 = new Node(5);
n3.next = n4;
let n5 = new Node(6);
n4.next = n5;
let n6 = new Node(7);
n5.next = n6;
n6.next = null;
 
let k = 4;
let data = 100;
 
print(insertatk(head, k, data));
 
// this code is contributed by Yash Agarwal(yashagarwal2852002)

Output

1 2 3 100 4 5 6 7

Time Complexity: O(N) where N is the size of the given linked list
Auxiliary Space: O(N) for call stack since using recursion

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!