Open In App

Program for Nth node from the end of a Linked List

Last Updated : 02 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a Linked List and a number N, write a function that returns the value at the Nth node from the end of the Linked List.

Linked-List

Examples:

Input: 1 -> 2 -> 3 -> 4, N = 3
Output: 2

Input: 35 -> 15 -> 4 -> 20, N = 4
Output: 35   

Naive Approach: Follow the given steps to solve the problem using this approach: 

  • Calculate the length of the Linked List. Let the length be len. 
  • Print the (len – n + 1)th node from the beginning of the Linked List. 

Below is the implementation of the above approach:

C
// C program to find N'th node from end
#include <stdio.h>
#include <stdlib.h>

/* Link list node */
typedef struct Node {
    int data;
    struct Node* next;
} Node;

/* Function to get the nth node from the last of a linked
 * list*/
void printNthFromLast(Node* head, int N)
{
    int len = 0, i;
    Node* temp = head;

    // Count the number of nodes in Linked List
    while (temp != NULL) {
        temp = temp->next;
        len++;
    }

    // Check if value of N is not
    // more than length of the linked list
    if (len < N)
        return;
    temp = head;

    // Get the (len-N+1)th node from the beginning
    for (i = 1; i < len - N + 1; i++)
        temp = temp->next;
    printf("%d", temp->data);
    return;
}

void push(struct Node** head_ref, int new_data)
{
    /* Allocate node */
    Node* new_node = (Node*)malloc(sizeof(Node));

    /* Put in the data */
    new_node->data = new_data;

    /* link the old list of the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

// Driver's Code
int main()
{

    /* Start with the empty list */
    struct Node* head = NULL;

    // create linked 35->15->4->20
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 35);
  
      // Function call
    printNthFromLast(head, 4);
    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find N'th node from
// end of linked list
import java.io.*;
class LinkedList {
    Node head; // head of the list

    /* Linked List node */
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    /* Function to get the Nth node from the last of a
       linked list */
    void printNthFromLast(int N)
    {
        int len = 0;
        Node temp = head;

        // 1) count the number of nodes in Linked List
        while (temp != null) {
            temp = temp.next;
            len++;
        }

        // check if value of N is not more than length of
        // the linked list
        if (len < N)
            return;

        temp = head;

        // 2) get the (len-N+1)th node from the beginning
        for (int i = 1; i < len - N + 1; i++)
            temp = temp.next;

        System.out.println(temp.data);
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    // Driver's code
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
        
          // Function call
        llist.printNthFromLast(4);
    }
} // This code is contributed by Rajat Mishra
Python3
# Python3 program to find
# N'th node from end

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


class LinkedList:
    def __init__(self):
        self.head = None

    # CreateNode and make linked list
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # Function to get the nth node from
    # the last of a linked list
    def printNthFromLast(self, n):
        temp = self.head  # Used temp variable

        length = 0
        while temp is not None:
            temp = temp.next
            length += 1

        # Print count
        if n > length:  # If entered location is greater
                       # than length of linked list
            print('Location is greater than the' +
                  ' length of LinkedList')
            return
        temp = self.head
        for i in range(0, length - n):
            temp = temp.next
        print(temp.data)


# Driver's Code
if __name__ == "__main__":
    llist = LinkedList()
    llist.push(20)
    llist.push(4)
    llist.push(15)
    llist.push(35)

    # Function call
    llist.printNthFromLast(4)

# This code is contributed by Yogesh Joshi
C#
// C# program to find N'th node from end of linked list
using System;

public class LinkedList {
    public Node head; // head of the list

    /* Linked List node */
    public class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }

    /* Function to get the nth node from the last of a
    linked list */
    void printNthFromLast(int N)
    {
        int len = 0;
        Node temp = head;

        // 1) count the number of nodes in Linked List
        while (temp != null) {
            temp = temp.next;
            len++;
        }

        // check if value of N is not more than length of
        // the linked list
        if (len < N)
            return;

        temp = head;

        // 2) get the (len-N+1)th node from the beginning
        for (int i = 1; i < len - N + 1; i++)
            temp = temp.next;

        Console.WriteLine(temp.data);
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    // Driver's code
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
    
          // Function call
        llist.printNthFromLast(4);
    }
}

// This code is contributed by Rajput-Ji
Javascript
// Simple Javascript program to find n'th node from end of linked list

  /* Linked List node */
  class Node {
      
      constructor(d)
      {
          this.data = d;
          this.next = null;
      }
  }

  /* Function to get the nth node from the last of a
     linked list */
  class LinkedList
  {

    constructor(d){
      this.head = d;
    }
  
  printNthFromLast(n)
  {
      let len = 0;
      let temp = this.head;

      // 1) count the number of nodes in Linked List
      while (temp != null) {
          temp = temp.next;
          len++;
      }

      // check if value of n is not more than length of
      // the linked list
      if (len < n)
          return;

      temp = this.head;

      // 2) get the (len-n+1)th node from the beginning
      for (let i = 1; i < len - n + 1; i++)
          temp = temp.next;

      console.log(temp.data);
  }

  /* Inserts a new Node at front of the list. */
  push(new_data)
  {
      /* 1 & 2: Allocate the Node &
                Put in the data*/
      let new_node = new Node(new_data);

      /* 3. Make next of new Node as head */
      new_node.next = this.head;

      /* 4. Move the head to point to new Node */
      this.head = new_node;
  }
  }
  
  /*Driver program to test above methods */
      let llist = new LinkedList();
      llist.push(20);
      llist.push(4);
      llist.push(15);
      llist.push(35);

      llist.printNthFromLast(4);
  
 // This code is contributed by Saurabh Jaiswal
C++14
// C++ program to find N'th node from end
#include <bits/stdc++.h>
using namespace std;

/* Link list node */
struct Node {
    int data;
    struct Node* next;
      
      Node(int x) {
        data = x;
          next = NULL;
    }
};

/* Function to get the Nth node from
   the last of a linked list*/
void printNthFromLast(struct Node* head, int N)
{
    int len = 0, i;
    struct Node* temp = head;

    // Count the number of nodes in Linked List
    while (temp != NULL) {
        temp = temp->next;
        len++;
    }

    // Check if value of N is not
    // more than length of the linked list
    if (len < N)
        return;

    temp = head;

    // Get the (len-N+1)th node from the beginning
    for (i = 1; i < len - N + 1; i++)
        temp = temp->next;

    cout << temp->data;

    return;
}

void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = new Node(new_data);

    /* link the old list of the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

// Driver's Code
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;

    // create linked 35->15->4->20
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 35);
    
      // Function call
    printNthFromLast(head, 4);
    return 0;
}

Output
35

Time complexity: O(M) where M is the size of the linked list
Auxiliary Space: O(1)

The given code implements a singly linked list in C and provides a function to print the Nth node from the end of the linked list.

Here is the algorithm of the code:

1.Define a struct called “Node” to represent each node of the linked list. It contains an integer data element and a pointer to the next node.

2.Define a function called “printNthFromLast” that takes two arguments: a pointer to the head of the linked list and an integer N representing the position of the node from the end.

3.Inside the “printNthFromLast” function, initialize a variable “len” to 0 and a temporary pointer “temp” to the head of the linked list.

4.Traverse the linked list using the temporary pointer “temp” and increment the “len” variable until “temp” becomes NULL.

5.Check if the value of N is less than or equal to the length of the linked list. If not, return from the function.

6.Reset the temporary pointer “temp” to the head of the linked list.

7.Traverse the linked list again, starting from the head, until the (len-N+1)th node is reached. Store the address of this node in the “temp” pointer.

8.Print the value of the “data” element of the “temp” node.

9.Define a function called “push” that takes two arguments: a double pointer to the head of the linked list and an integer representing the data to be inserted.

10.Inside the “push” function, allocate memory for a new node using the “malloc” function.

11.Set the “data” element of the new node to the input data value and set its “next” pointer to point to the current head of the linked list.

12.Update the head pointer to point to the new node.

13.In the main function, initialize the head pointer to NULL.

14.Insert elements 20, 4, 15, and 35 into the linked list using the “push” function.

15.Call the “printNthFromLast” function with the head pointer and the value 4 as arguments. This should print the value of the 4th node from the end of the linked list, which is 35.

Below is a recursive code for the same method. Thanks to Anuj Bansal for providing the following code.

C++
void printNthFromLast(struct Node* head, int N)
{
    static int i = 0;
    if (head == NULL)
        return;
    printNthFromLast(head->next, N);
    if (++i == N)
        cout<<head->data;
}
C
void printNthFromLast(struct Node* head, int N)
{
    static int i = 0;
    if (head == NULL)
        return;
    printNthFromLast(head->next, N);
    if (++i == N)
        printf("%d", head->data);
}
Java
import java.io.*;
static void printNthFromLast(Node head, int N)
{
    int i = 0;

    if (head == null)
        return;
    printNthFromLast(head.next, N);

    if (++i == N)
        System.out.print(head.data);
}

// This code is contributed by rutvik_56.
C#
static void printNthFromLast(Node head, int N)
{
    static int i = 0;

    if (head == null)
        return;
    printNthFromLast(head.next, N);

    if (++i == N)
        Console.Write(head.data);
}

// This code is contributed by pratham76.
Javascript
function printNthFromLast(head , N)
{
    function i = 0;

    if (head == null)
        return;
    printNthFromLast(head.next, N);

    if (++i == N)
        document.write(head.data);
}


// This code is contributed by gauravrajput1
Python3
def printNthFromLast(head, N):
    
    i = 0
    if (head == None)
        return
    printNthFromLast(head.next, N);
    i += 1
    if (i == N):
        print(head.data)
    
    
# This code is contributed by sunils0ni.

Time Complexity: O(M) where M is the length of the linked list. 
Auxiliary Space: O(M) for call stack

Nth node from the end of a Linked List using two pointers:

As Nth node from the end equals to (Length – N + 1)th node from the start, so the idea is to Maintain two pointers starting from the head of the Linked-List and move one pointer to the Nth node from the start and then move both the pointers together until the pointer at the Nth position reaches the last node. Now the pointer which was moved later points at the Nth node from the end of the Linked-List

Below image is a dry run of the above approach:


Follow the given steps to solve the problem:

  • Maintain two pointers main_ptr and ref_ptr
  • Move ref_ptr to the Nth node from the start
  • Now move both main_ptr and ref_ptr, until the ref_ptr reaches the last node
  • Now print the data of the main_ptr, as it is at the Nth node from the end

Below is the implementation of the above approach: 

C++
// C++ program to find n-th node
// from the end of the linked list.

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

struct node {
    int data;
    node* next;
    node(int val)
    {
        data = val;
        next = NULL;
    }
};

struct llist {

    node* head;
    llist() { head = NULL; }

    // insert operation at the beginning of the list.
    void insertAtBegin(int val)
    {
        node* newNode = new node(val);
        newNode->next = head;
        head = newNode;
    }

    // finding n-th node from the end.
    void nthFromEnd(int n)
    {
        // create two pointers main_ptr and ref_ptr
        // initially pointing to head.
        node* main_ptr = head;
        node* ref_ptr = head;

        // if list is empty, return
        if (head == NULL) {
            cout << "List is empty" << endl;
            return;
        }

        // move ref_ptr to the n-th node from beginning.
        for (int i = 1; i < n; i++) {
            ref_ptr = ref_ptr->next;
            if (ref_ptr == NULL) {
                cout << n
                     << " is greater than no. of nodes in "
                        "the list"
                     << endl;
                return;
            }
        }

        // move ref_ptr and main_ptr by one node until
        // ref_ptr reaches end of the list.
        while (ref_ptr != NULL && ref_ptr->next != NULL) {
            ref_ptr = ref_ptr->next;
            main_ptr = main_ptr->next;
        }
        cout << "Node no. " << n
             << " from end is: " << main_ptr->data << endl;
    }
};

// Driver's code
int main()
{
    llist ll;

    ll.insertAtBegin(20);
    ll.insertAtBegin(4);
    ll.insertAtBegin(15);
    ll.insertAtBegin(35);

    // Function call
    ll.nthFromEnd(4);

    return 0;
}

// This code is contributed by sandeepkrsuman.
Java
// Java program to find N'th
// node from end
import java.io.*;
class LinkedList {
    Node head; // head of the list

    /* Linked List node */
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    /* Function to get the
      Nth node from end of list */
    void printNthFromLast(int N)
    {
        Node main_ptr = head;
        Node ref_ptr = head;

        int count = 0;
        if (head != null) {
            while (count < N) {
                if (ref_ptr == null) {
                    System.out.println(
                        N + " is greater than the no "
                        + " of nodes in the list");
                    return;
                }
                ref_ptr = ref_ptr.next;
                count++;
            }

            if (ref_ptr == null) {

                if (head != null)
                    System.out.println("Node no. " + N
                                       + " from last is "
                                       + head.data);
            }
            else {

                while (ref_ptr != null) {
                    main_ptr = main_ptr.next;
                    ref_ptr = ref_ptr.next;
                }
                System.out.println("Node no. " + N
                                   + " from last is "
                                   + main_ptr.data);
            }
        }
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    // Driver's code
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);

        // Function call
        llist.printNthFromLast(4);
    }
}
// This code is contributed by Rajat Mishra
C#
// C# program to find N'th node from end
using System;

public class LinkedList {
    Node head; // head of the list

    /* Linked List node */
    public class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }

    /* Function to get the Nth node from end of list */
    void printNthFromLast(int N)
    {
        Node main_ptr = head;
        Node ref_ptr = head;

        int count = 0;
        if (head != null) {
            while (count < N) {
                if (ref_ptr == null) {
                    Console.WriteLine(
                        N + " is greater than the no "
                        + " of nodes in the list");
                    return;
                }
                ref_ptr = ref_ptr.next;
                count++;
            }

            if (ref_ptr == null) {
                head = head.next;
                if (head != null)
                    Console.WriteLine("Node no. " + N
                                      + " from last is "
                                      + main_ptr.data);
            }
            else {
                while (ref_ptr != null) {
                    main_ptr = main_ptr.next;
                    ref_ptr = ref_ptr.next;
                }
                Console.WriteLine("Node no. " + N
                                  + " from last is "
                                  + main_ptr.data);
            }
        }
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                    Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    // Driver's code
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
        
          // Function call
        llist.printNthFromLast(4);
    }
}

/* This code is contributed by PrinciRaj1992 */
Javascript
// javascript program to find n'th 
// node from end using slow and
// fast pointers
var head; // head of the list

    /* Linked List node */
     class Node {
            constructor(val) {
                this.data = val;
                this.next = null;
            }
        }
        
    /*
     * Function to get the nth node from end of list
     */
    function printNthFromLast(n) 
    {
        var main_ptr = head;
        var ref_ptr = head;

        var count = 0;
        if (head != null) {
            while (count < n) {
                if (ref_ptr == null) {
                    document.write(n + " is greater than the no " +
                    " of nodes in the list");
                    return;
                }
                ref_ptr = ref_ptr.next;
                count++;
            }

            if (ref_ptr == null) {

                if (head != null)
                    document.write("Node no. " + n + " from last is " + head.data);
            } else {

                while (ref_ptr != null) {
                    main_ptr = main_ptr.next;
                    ref_ptr = ref_ptr.next;
                }
                document.write("Node no. " + n + " from last is " + main_ptr.data);
            }
        }
    }

    /* Inserts a new Node at front of the list. */
     function push(new_data) {
        /*
         * 1 & 2: Allocate the Node & Put in the data
         */
        var new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    /* Driver program to test above methods */
    
        push(20);
        push(4);
        push(15);
        push(35);

        printNthFromLast(4);

// This code is contributed by Rajput-Ji 
Python3
# Python3 program to find N'th node from end

# Node class


class Node:

    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def printNthFromLast(self, N):
        main_ptr = self.head
        ref_ptr = self.head

        count = 0
        if(self.head is not None):
            while(count < N):
                if(ref_ptr is None):
                    print("%d is greater than the no. pf nodes in list" % (N))
                    return

                ref_ptr = ref_ptr.next
                count += 1

        if(ref_ptr is None):
            self.head = self.head.next
            if(self.head is not None):
                print("Node no. %d from last is % d "
                      % (N, main_ptr.data))
            #For a single Node
            if(self.head is None):
                print("Node no. %d from last is % d "
                      % (N, main_ptr.data))
        else:
          
            while(ref_ptr is not None):
                main_ptr = main_ptr.next
                ref_ptr = ref_ptr.next

            print("Node no. %d from last is %d"
                  % (N, main_ptr.data))


# Driver's code
if __name__ == '__main__':
    llist = LinkedList()
    llist.push(20)
    llist.push(4)
    llist.push(15)
    llist.push(35)

    # Function call
    llist.printNthFromLast(4)

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)



Output
35->15->4->20->NULL
Node no. 4 from end is: 35

Time Complexity: O(M) where M is the length of the linked list.
Auxiliary Space: O(1)


Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.



Previous Article
Next Article

Similar Reads

Cpp14 Program For Printing Nth Node From The End Of A Linked List (Duplicate)
Given a Linked List and a number n, write a function that returns the value at the n'th node from the end of the Linked List.For example, if the input is below list and n = 3, then output is "B" Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Method 1 (Use length of linked list) 1) Calculate the length of Linked
5 min read
C++ Program For Printing Nth Node From The End Of A Linked List
Given a Linked List and a number n, write a function that returns the value at the n'th node from the end of the Linked List.For example, if the input is below list and n = 3, then output is "B" Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Method 1 (Use length of linked list): Calculate the length of Linked Li
4 min read
Java Program For Printing Nth Node From The End Of A Linked List
Given a Linked List and a number n, write a function that returns the value at the n'th node from the end of the Linked List.For example, if the input is below the list and n = 3, then the output is "B". Recommended: Please solve it on "PRACTICE" first, before moving on to the solution.Method 1 (Use length of linked list) 1) Calculate the length of
5 min read
Java Program For Printing Nth Node From The End Of A Linked List(Duplicate)
Given a Linked List and a number n, write a function that returns the value at the n'th node from the end of the Linked List.For example, if the input is below list and n = 3, then output is "B" Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Method 1 (Use length of linked list) 1) Calculate the length of Linked
2 min read
Recursive Approach to find nth node from the end in the linked list
Find the nth node from the end in the given linked list using a recursive approach. Examples: Input : list: 4-&gt;2-&gt;1-&gt;5-&gt;3 n = 2 Output : 5 Algorithm: findNthFromLast(head, n, count, nth_last) if head == NULL then return findNthFromLast(head-&gt;next, n, count, nth_last) count = count + 1 if count == n then nth_last = head findNthFromLas
8 min read
Remove Nth node from end of the Linked List
Given a linked list. The task is to remove the Nth node from the end of the linked list. Examples: Input : 1-&gt;2-&gt;3-&gt;4-&gt;5 , N = 2 Output : 1-&gt;2-&gt;3-&gt;5 Input : 7-&gt;8-&gt;4-&gt;3-&gt;2 , N = 1 Output : 7-&gt;8-&gt;4-&gt;3 Prerequisites: 1. Delete a node from the linked list. 2. Find the nth node from the end of the linked listApp
15+ min read
XOR Linked List - Find Nth Node from the end
Given a XOR linked list and an integer N, the task is to print the Nth node from the end of the given XOR linked list. Examples: Input: 4 –&gt; 6 –&gt; 7 –&gt; 3, N = 1 Output: 3 Explanation: 1st node from the end is 3.Input: 5 –&gt; 8 –&gt; 9, N = 4 Output: Wrong Input Explanation: The given Xor Linked List contains only 3 nodes. Approach: Follow
15+ min read
Delete Nth node from the end of the given linked list
Given a linked list and an integer N, the task is to delete the Nth node from the end of the given linked list. Examples: Input: 2 -&gt; 3 -&gt; 1 -&gt; 7 -&gt; NULL, N = 1 Output: The created linked list is: 2 3 1 7 The linked list after deletion is: 2 3 1 Input: 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; NULL, N = 4 Output: The created linked list is: 1 2 3
13 min read
Javascript Program For Swapping Kth Node From Beginning With Kth Node From End In A Linked List
Given a singly linked list, swap kth node from beginning with kth node from end. Swapping of data is not allowed, only pointers should be changed. This requirement may be logical in many situations where the linked list data part is huge (For example student details line Name, RollNo, Address, ..etc). The pointers are always fixed (4 bytes for most
5 min read
C++ Program For Swapping Kth Node From Beginning With Kth Node From End In A Linked List
Given a singly linked list, swap kth node from beginning with kth node from end. Swapping of data is not allowed, only pointers should be changed. This requirement may be logical in many situations where the linked list data part is huge (For example student details line Name, RollNo, Address, ..etc). The pointers are always fixed (4 bytes for most
5 min read