Find the nth node from the last linked list in C++ using recursive method

Given a singly linked list and a positive integer N as input. The goal is to find the Nth node from the end of the given list using recursion. If the input list has nodes a → b → c → d → e → f and N is 4, then the fourth node from the last will be c.

We will first traverse until the last node in the list and when returning from the recursive (backtracking) increment count. When count equals N, a pointer to the current node is returned as the result.

Let's look at various input and output scenarios for this -

Input- List: - 1 → 5 → 7 → 12 → 2 → 96 → 33 N= 3

Output− The Nth node from the last is: 2

Explanation− The third node is 2.

Input− List: - 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>

Output- Node does not exist .

Explanation - The list only has 7 nodes, so there cannot be an 8th node from the bottom.

The method used in the following program is as follows

In this approach we will first use recursion to reach the end of the list and while backtracking we will increment a static count variable. Once count equals the input N, the current node pointer is returned.

• Take a structure Node with an int data part and use Node as the next pointer.

  • Adopt structure Node and int data part. p>

  • The function addtohead(Node** head, int data) is used to add nodes to the head and create a one-way linked list.

  • Use the above function to create a one-way linked list, with the head as the pointer to the first node.

  • The function display(Node* head) is used to print the linked list from the beginning

  • Set N as a positive integer.

  • Function findNode(Node* head, int n1) gets the pointer to head and n1, and prints the result when the n1th node from the bottom is found.

  • Use blast as a pointer to the n1th node from the last.

  • Call searchNthLast(head, n1, &nlast) to find the node.

  • Function searchNthLast(Node* head, int n1, Node** nlast) returns a pointer to the n1th last node in the linked list from the end, the head is the first node .

  • Use static count variables.

  • If head is NULL, nothing is returned.

  • Get tmp=head->next.

  • Call searchNthLast(tmp, n1, nlast) to recursively traverse until the last node.

  • Then add 1 to count.

  • If count becomes equal to n1 then set *nlast=head.

  • Finally print the value of the node pointed to by nlast as the result.

  Example

  #include <bits/stdc++.h>
  using namespace std;
  struct Node {
     int data;
     Node* next;
  };
  void addtohead(Node** head, int data){
     Node* nodex = new Node;
     nodex->data = data;
     nodex->next = (*head);
     (*head) = nodex;
  }
  void searchNthLast(Node* head, int n1, Node** nlast){
     static int count=0;
     if (head==NULL){
        return;
     }
     Node* tmp=head->next;
     searchNthLast(tmp, n1, nlast);
     count = count + 1;
     if (count == n1){
        *nlast = head;
     }
  }
  void findNode(Node* head, int n1){
     Node* nlast = NULL;
     searchNthLast(head, n1, &nlast);
     if (nlast == NULL){
        cout << "Node does not exists";
     }
     else{
        cout << "Nth Node from the last is: "<< nlast->data;
     }
  }
  void display(Node* head){
     Node* curr = head;
     if (curr != NULL){
        cout<<curr->data<<" ";
        display(curr->next);
     }
  }
  int main(){
     Node* head = NULL;
     addtohead(&head, 20);
     addtohead(&head, 12);
     addtohead(&head, 15);
     addtohead(&head, 8);
     addtohead(&head, 10);
     addtohead(&head, 4);
     addtohead(&head, 5);
     int N = 2;
     cout<<"Linked list is :"<<endl;
     display(head);
     cout<<endl;
     findNode(head, N);
     return 0;
  }

  Output

  If we run the above code it will generate the following output

  Linked list is :
  5 4 10 8 15 12 20
  Nth Node from the last is: 12

The above is the detailed content of Find the nth node from the last linked list in C++ using recursive method. For more information, please follow other related articles on the PHP Chinese website!