Given a Linked List and a number n, write a function that returns the value at the n’th node from end of the Linked List.

Method 1 (Use length of linked list)
1) Calculate the length of Linked List. Let the length be len.
2) Print the (len – n + 1)th node from the begining of the Linked List.

C Programming:

// Simple C program to find n'th node from end
#include<stdio.h>
#include<stdlib.h>
 
/* Link list node */
struct node
{
  int data;
  struct node* next;
};
 
/* 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;
 
    // 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 (n-len+1)th node from the begining
    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 */
  struct node* new_node =
          (struct node*) malloc(sizeof(struct node));
 
  /* put in the data  */
  new_node->data  = new_data;
 
  /* link the old list off the new node */
  new_node->next = (*head_ref);
 
  /* move the head to point to the new node */
  (*head_ref)    = new_node;
}
 
/* Drier program to test above function*/
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);
 
  printNthFromLast(head, 5);
  return 0; 
}

Output:

35
[ad type=”banner”]

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

C Programming:

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

Time Complexity: O(n) where n is the length of linked list.
Method 2 (Use two pointers)
Maintain two pointers – reference pointer and main pointer. Initialize both reference and main pointers to head. First move reference pointer to n nodes from head. Now move both pointers one by one until reference pointer reaches end. Now main pointer will point to nth node from the end. Return main pointer.

Python Programming:

# Python program to find n'th node from end using slow
# and fast pointer
 
# 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
 
        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 program to test above function
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(35)
 
llist.printNthFromLast(4)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

Output:

Node no. 4 from last is 35

Time Complexity: O(n) where n is the length of linked list

[ad type=”banner”]

Categorized in:

Linked ListSingly Linked List

Tagged in:

, , , , , , , , , , , , ,