Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Linked list articles

Insert a node after the n-th node from the end

Aman Sharma

Last Updated on March 10, 2022 by Ria Pathak

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

Insert a node after the n-th node from the end of Linked list.

Problem Statement Understanding

In this problem, we are given a linked list, an integer N and another integer X. We have to traverse till the Nth node from the end and insert X there.

Suppose the linked list is 2 -> 4 -> 7 -> 8, N=4 and X=2. Here, we have to insert 2 after the 4th node from the end. Now, the 4th node from the end is the head node (2). So, we will have to insert the new node after the head node.

The final linked list will be 2 -> 2 -> 4 -> 7 -> 8.

Input:

Output:

Explanation: 4th node from the end is 2 and insertion has been done after this node.

We are going to see two approaches to this problem. One approach will make use of finding the length of the given linked list, and the other approach will use the slow and fast pointer method.

Approach#1

In this approach, we will first find the length of the linked list. Let it be K. Now, we will traverse the list from the 1st node to the (K-N+1)th node from the beginning and insert the given new node after this node. This approach requires two full traversals of the list.

Algorithm

  • If the linked list is empty, we will simply terminate the method.
  • If the base case fails, then we will proceed further and find the length of the linked list using a while loop.
  • If the length of the linked list is K, then traverse from the 1st node to the (K-N+1)th node. After the traversal, insert the given node at that position.

Code Implementation

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};

struct Node* getNode(int data)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// Function to insert a node at the n-th position from the end
void insertAfterNthNode(struct Node* head, int n, int x)
{
    if (head == NULL)
        return;

    struct Node* newNode = getNode(x);
    struct Node* ptr = head;
    int len = 0, i;
 
    // Calculation the length of the linked list
    while (ptr != NULL) {
        len++;
        ptr = ptr->next;
    }
 
    // Traverse till the n-th node from the end
    ptr = head;
    for (i = 1; i <= (len - n); i++)
        ptr = ptr->next;
 
    // Insert the given node at this position
    newNode->next = ptr->next;
    ptr->next = newNode;
}
 
void printList(struct Node* head)
{
    while (head != NULL) {
        printf("%d ",&head->data);
        head = head->next;
    }
}
 
int main()
{

    struct Node* head = getNode(2);
    head->next = getNode(4);
    head->next->next = getNode(7);
    head->next->next->next = getNode(8);
    int n = 4;
    int x = 2;
 
    printf("Original Linked List: ");
    printList(head);
 
    insertAfterNthNode(head, n, x);
 
    printf("\nLinked List After Insertion: ");
    printList(head);
 
    return 0;
}


#include <bits stdc++.h>
using namespace std;
 
struct Node {
    int data;
    Node* next;
};

Node* getNode(int data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
 
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// Function to insert a node at the n-th position from the end
void insertAfterNthNode(Node* head, int n, int x)
{
    if (head == NULL)
        return;

    Node* newNode = getNode(x);
    Node* ptr = head;
    int len = 0, i;
 
    // Calculation the length of the linked list
    while (ptr != NULL) {
        len++;
        ptr = ptr->next;
    }
 
    // Traverse till the n-th node from the end
    ptr = head;
    for (i = 1; i <= (len - n); i++)
        ptr = ptr->next;
 
    // Insert the given node at this position
    newNode->next = ptr->next;
    ptr->next = newNode;
}
 
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
 
int main()
{

    Node* head = getNode(2);
    head->next = getNode(4);
    head->next->next = getNode(7);
    head->next->next->next = getNode(8);
    int n = 4;
    int x = 2;
 
    cout << "Original Linked List: ";
    printList(head);
 
    insertAfterNthNode(head, n, x);
 
    cout << "\nLinked List After Insertion: ";
    printList(head);
 
    return 0;
}

public class PrepBytes
{

static class Node
{
    int data;
    Node next;
}

static Node getNode(int data)
{

    Node newNode = new Node();

    newNode.data = data;
    newNode.next = null;
    return newNode;
}

static void insertAfterNthNode(Node head, int n, int x)
{

    if (head == null)
        return;

    Node newNode = getNode(x);
    Node ptr = head;
    int len = 0, i;

    while (ptr != null)
    {
        len++;
        ptr = ptr.next;
    }

    ptr = head;
    for (i = 1; i <= (len - n); i++)
        ptr = ptr.next;
 
    newNode.next = ptr.next;
    ptr.next = newNode;
}
 

static void printList(Node head)
{
    while (head != null)
    {
        System.out.print(head.data + " ");
        head = head.next;
    }
}
 

public static void main(String[] args)
{

    Node head = getNode(2);
    head.next = getNode(4);
    head.next.next = getNode(7);
    head.next.next.next = getNode(8);
 
    int n = 4, x = 2;
 
    System.out.print("Original Linked List: ");
    printList(head);
 
    insertAfterNthNode(head, n, x);
    System.out.println();
    System.out.print("Linked List After Insertion: ");
    printList(head);
}
}

# A linked list Node
class Node:
	def __init__(self, data):
		self.data = data
		self.nextNode = None

# function to create and return a Node
def getNode(data):

	newNode = Node(data)
	return newNode

# function to insert a Node at required position
def insertPos(headNode, position, data):
	head = headNode
	
	if (position < 1):	
		print("Invalid position!")
	
	if position == 1:
		newNode = Node(data)
		newNode.nextNode = headNode
		head = newNode
			
	else:
	
		while (position != 0):		
			position -= 1

			if (position == 1):

				newNode = getNode(data)
				newNode.nextNode = headNode.nextNode
				headNode.nextNode = newNode
				break
			
			headNode = headNode.nextNode
			if headNode == None:
				break		
		if position != 1:
			print("position out of range")	
	return head
	
def printList(head):
	while (head != None):	
		print(' ' + str(head.data), end = '')
		head = head.nextNode
	print()
	
if __name__=='__main__':
	
	head = getNode(1)
	head.nextNode = getNode(2)
	head.nextNode.nextNode = getNode(3)
	head.nextNode.nextNode.nextNode = getNode(4)
	head.nextNode.nextNode.nextNode.nextNode = getNode(5)
	print("Linked list before insertion: ", end='')
	printList(head)
	data = 6
	position = 2
	head = insertPos(head, position, data)
	print("Linked list after insertion of 6 at position 2: ", end = '')
	printList(head)

Output
Original Linked List : 2 4 7 8
Linked List after Insertion : 2 2 4 7 8

Time Complexity: O(N), as no nested traversal is needed.

Space Complexity: O(1), as only temporary variables are being created.

Approach#2

This approach uses the two pointer method. One slow pointer and another fast pointer. First, we will move the fast pointer up to the nth node from the beginning. Now, make the slow pointer point to the 1st node. Now, we will simultaneously move both the pointers. When the fast pointer reaches the end, the slow pointer will be pointing to the Nth node from the end. The best part about this approach is that it requires only a single traversal.

Algorithm

  • If the linked list is empty, we will simply terminate the method.
  • Create two pointers, slow and fast.
  • Point the fast pointer to the Nth node from the beginning, and the slow pointer to the 1st node of the linked list.
  • Simultaneously move both the pointers. When the fast pointer will reach the end, the slow pointer will be pointing to the Nth node from the end.
  • Finally, insert the new node just after the slow pointer.

Dry Run

Code Implementation

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
 
// function to get a new node
struct Node* getNode(int data)
{
    // allocate memory for the node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 
    // put in the data
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// function to insert a node after the
// nth node from the end
void insertAfterNthNode(struct Node* head, int n, int x)
{
    // if list is empty
    if (head == NULL)
        return;
 
    // get a new node for the value 'x'
   struct Node* newNode = getNode(x);
 
    // Initializing the slow and fast pointers
   struct Node* slow_ptr = head;
    struct Node* fast_ptr = head;
 
    // move 'fast_ptr' to point to the nth node
    // from the beginning
    for (int i = 1; i <= n - 1; i++)
        fast_ptr = fast_ptr->next;
 
    // iterate until 'fast_ptr' points to the
    // last node
    while (fast_ptr->next != NULL) {
 
        // move both the pointers to the
        // respective next nodes
        slow_ptr = slow_ptr->next;
        fast_ptr = fast_ptr->next;
    }
 
    // insert the 'newNode' by making the
    // necessary adjustment in the links
    newNode->next = slow_ptr->next;
    slow_ptr->next = newNode;
}
 
// function to print the list
void printList(struct Node* head)
{
    while (head != NULL) {
        printf("%d ",head->data);
        head = head->next;
    }
}
 
// Driver program to test above
int main()
{
    // Creating list 1->3->4->5
    struct Node* head = getNode(1);
    head->next = getNode(3);
    head->next->next = getNode(4);
    head->next->next->next = getNode(5);
 
    int n = 4, x = 2;
 
    printf("Original Linked List: ");
    printList(head);
 
    insertAfterNthNode(head, n, x);
 
    printf("\nLinked List After Insertion: ");
    printList(head);
 
    return 0;
}

#include <bits stdc++.h>
using namespace std;
 

struct Node {
    int data;
    Node* next;
};
 
Node* getNode(int data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// Function to insert the given node at 
// the n-th position from the end
void insertAfterNthNode(Node* head, int n, int x)
{
    if (head == NULL)
        return;
 
    Node* newNode = getNode(x);
 
    // Initializing both the pointers
    Node* slow_ptr = head;
    Node* fast_ptr = head;
 
    for (int p = 1; p <= n - 1; p++)
        fast_ptr = fast_ptr->next;
 
    // Making the fast pointer reach the end
    while (fast_ptr->next != NULL) {
        slow_ptr = slow_ptr->next;
        fast_ptr = fast_ptr->next;
    }
    // Inserting the new node after the the slow pointer
    newNode->next = slow_ptr->next;
    slow_ptr->next = newNode;
}
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
 

int main()
{

    Node* head = getNode(2);
    head->next = getNode(4);
    head->next->next = getNode(7);
    head->next->next->next = getNode(8);
    int n = 4;
    int x = 2;
 
    cout << "Original Linked List: ";
    printList(head);
 
    insertAfterNthNode(head, n, x);
 
    cout << "\nLinked List After Insertion: ";
    printList(head);
 
    return 0;
}


public class PrepBytes
{


static class Node
{
    int data;
    Node next;
}


static Node getNode(int data)
{

    Node newNode = new Node();


    newNode.data = data;
    newNode.next = null;
    return newNode;
}


static void insertAfterNthNode(Node head,
                            int n, int x)
{

    if (head == null)
        return;

    Node newNode = getNode(x);


    Node slow_ptr = head;
    Node fast_ptr = head;


    for (int i = 1; i <= n - 1; i++)
        fast_ptr = fast_ptr.next;

    while (fast_ptr.next != null)
    {


        slow_ptr = slow_ptr.next;
        fast_ptr = fast_ptr.next;
    }

    newNode.next = slow_ptr.next;
    slow_ptr.next = newNode;
}


static void printList(Node head)
{
    while (head != null)
    {
        System.out.print(head.data + " ");
        head = head.next;
    }
}


public static void main(String[] args)
{

    Node head = getNode(2);
    head.next = getNode(4);
    head.next.next = getNode(7);
    head.next.next.next = getNode(8);

    int n = 4, x = 2;
    System.out.println("Original Linked List: ");
    printList(head);

    insertAfterNthNode(head, n, x);
    System.out.println();
    System.out.println("Linked List After Insertion: ");
    printList(head);
}
}


class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

def getNode(data) :

	newNode = Node(0)
	newNode.data = data
	newNode.next = None
	return newNode

# function to insert a node after the
# nth node from the end
def insertAfterNthNode(head, n, x) :

	if (head == None):
		return
 
	newNode = getNode(x)
 
	# Initializing both the pointers
	slow_ptr = head
	fast_ptr = head
 
	for p in range(1, n):
		fast_ptr = fast_ptr.next
 
	# Making the fast pointer reach the end
	while (fast_ptr.next != None):
		slow_ptr = slow_ptr.next
		fast_ptr = fast_ptr.next
	
	# Inserting the new node after the the slow pointer
	newNode.next = slow_ptr.next
	slow_ptr.next = newNode

def printList( head) :

	while (head != None):
	
		print(head.data ,end = " ")
		head = head.next
	
head = getNode(2)
head.next = getNode(4)
head.next.next = getNode(7)
head.next.next.next = getNode(8)

n = 4
x = 2

print("Original Linked List: ")
printList(head)

insertAfterNthNode(head, n, x)
print()
print("Linked List After Insertion: ")
printList(head)

Output
Original Linked List : 2 4 7 8
Linked List after Insertion : 2 2 4 7 8

Time Complexity: O(N), as no nested traversal is needed.

Space Complexity: O(1), as only temporary variables are being created.

So, in this article, we have tried to explain the most efficient approach to insert a node after the Nth node from the end. We have shown two approaches here. Both approaches take O(N) time, but the second one is more efficient as it only requires a single traversal of the list. The slow and fast pointer technique is a must-know for coding interviews.

If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post