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->7Input: 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:
- Create a temporary node.
- Now insert the temporary node before head and change the head pointer to point the temporary node.
- Approach: Follow the steps mentioned below:
- Insert a node in between first and last node of linked list
- Approach: Follow the steps mentioned below:
- Call the recursive function to reach to the desired position.
- If the position is greater than the length of the list then insertion is not possible.
- If not, then insert the new node at the desired position.
- Approach: Follow the steps mentioned below:
- Insert a node at the end of linked list
- Approach: Follow the steps mentioned below:
- Recursively move to the end of the linked list.
- Insert the new node at the end of the list.
- Approach: Follow the steps mentioned below:
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 nullptrusing namespace std;// Structure of the node of linked liststruct node { int item; node* nxt; node(int item, node* t) { this->item = item; (*this).nxt = t; }};// Function to insert a node// at the first positionnode* insertAtFirst(node*& listHead, node* x){ node* temp = listHead; x->nxt = temp; listHead = temp = x; return temp;}// Function to insert a node// at the last positionnode* 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 lastnode* 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 recursionvoid print(node* head){ if (head == null) { return; } cout << head->item << " "; print(head->nxt);}// Driver codeint 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 listclass GFG{// Structure of the node of linked liststatic 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 positionstatic node insertAtFirst(node listHead, node x){ x.nxt = listHead; listHead = null; listHead = x; return listHead;}// Function to insert a node// at the last positionstatic 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 laststatic 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 recursionstatic void print(node head){ if (head == null) { return; } System.out.print(head.item + " "); print(head.nxt);}// Driver codepublic 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 Listdef 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 Recursiondef 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 codeif __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 listusing System;public class GFG{// Structure of the node of linked listclass 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 positionstatic node insertAtFirst(node listHead, node x){ x.nxt = listHead; listHead = null; listHead = x; return listHead;}// Function to insert a node// at the last positionstatic 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 laststatic 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 recursionstatic void print(node head){ if (head == null) { return; } Console.Write(head.item + " "); print(head.nxt);}// Driver codepublic 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 listclass node { constructor(item, t) { this.item = item; this.nxt = t; }};// Function to insert a node// at the first positionfunction insertAtFirst(listHead, x) { x.nxt = listHead; listHead = null; listHead = x; return listHead;}// Function to insert a node// at the last positionfunction 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 lastfunction 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 recursionfunction _print(head) { if (head == null) { return; } document.write(head.item + " "); _print(head.nxt);}// Driver codelet head = new node(1, null);// Creating a linked list of length 15for (let i = 2; i < 16; i++) insertAtEnd(head, new node(i, null));// Insert node with value 100 // at 4th positionhead = insertInBetween(head, new node(100, null), 4);// Insert node with value 101 // at 200th positionhead = insertInBetween(head, new node(101, null), 200);// Insert node with value 100 // at 1st positionhead = insertAtFirst(head, new node(100, null));// Insert node with value 100 // at the end positionhead = 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 codeimport 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 approachclass Node: def __init__(self, data): self.data = data self.next = Nonedef 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 headdef printList(head): temp = head while(temp is not None): print(temp.data, end=" ") temp = temp.next# driver codehead = Node(1)n1 = Node(2)head.next = n1n2 = Node(3)n1.next = n2n3 = Node(4)n2.next = n3n4 = Node(5)n3.next = n4n5 = Node(6)n4.next = n5n6 = Node(7)n5.next = n6n6.next = Nonek = 4data = 100printList(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 listusing 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 approachclass 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 codelet 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
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!
