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

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 
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);
}
}

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 
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);
}
}

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.

Previous post Make middle node the head in a linked list
Next post Implementing Iterator pattern of a single linked list

Leave a Reply

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