{"id":27031,"date":"2018-01-02T20:58:58","date_gmt":"2018-01-02T15:28:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27031"},"modified":"2018-01-02T20:58:58","modified_gmt":"2018-01-02T15:28:58","slug":"java-algorithm-find-nth-node-end-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-find-nth-node-end-linked-list\/","title":{"rendered":"Java Algorithm – Find n\u2019th node from the end of a Linked List"},"content":{"rendered":"

Given a Linked List and a number n, write a function that returns the value at the n\u2019th node from end of the Linked List.<\/p>\n

Method 1 (Use length of linked list)<\/strong>
\n1) Calculate the length of Linked List. Let the length be len.
\n2) Print the (len \u2013 n + 1)th node from the begining of the Linked List.<\/p>\n

Java Programming:<\/strong><\/p>\n

<\/div> 
\/\/ Simple Java program to find n'th node from end of linked listclass 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 (n-len+1)th node from the begining        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;    }     \/*Drier program to test above methods *\/    public static void main(String [] args)    {        LinkedList llist = new LinkedList();        llist.push(20);        llist.push(4);        llist.push(15);        llist.push(35);         llist.printNthFromLast(4);    }}\/\/ This code is contributed by Rajat Mishra<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
35<\/pre>\n[ad type=”banner”]\n
Following is a recursive C code for the same method. Thanks to Anuj Bansal for providing following code.<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
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);}<\/code><\/pre> <\/div>\n
Time Complexity:<\/strong> O(n) where n is the length of linked list.
\nMethod 2 (Use two pointers) <\/strong>
\nMaintain two pointers \u2013 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.<\/p>\n
Java Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ Java program to find n'th node from end using slow and\/\/ fast pointersclass 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++;            }            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;    }     \/*Drier program to test above methods *\/    public static void main(String [] args)    {        LinkedList llist = new LinkedList();        llist.push(20);        llist.push(4);        llist.push(15);        llist.push(35);         llist.printNthFromLast(4);    }} \/\/ This code is contributed by Rajat Mishra<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Node no. 4 from last is 35<\/pre>\n
Time Complexity:<\/strong> O(n) where n is the length of linked list<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Java Algorithm – Find n\u2019th node from the end of a Linked List – Linked List – Given a Linked List and a number n, write a function that returns the value<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[80490,80665,80661,80492,80659,80489,80493,80666,80660,80491],"class_list":["post-27031","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-singly-linked-list","tag-delete-nth-element-in-linked-list","tag-delete-nth-element-in-linked-list-java","tag-delete-nth-node-from-end-of-linked-list","tag-find-middle-element-in-linked-list-java","tag-find-nth-element-in-linked-list","tag-find-nth-element-in-linked-list-c","tag-find-nth-to-last-element-in-a-linked-list-recursion","tag-linked-list-in-cc-delete-a-node-at-nth-position","tag-remove-nth-node-from-end-of-list-c","tag-search-a-node-in-linked-list-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27031","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27031"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27031\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27031"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27031"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27031"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}