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:

[pastacode lang=”c” manual=”%2F%2F%20Simple%20C%20program%20to%20find%20n’th%20node%20from%20end%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20int%20data%3B%0A%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20get%20the%20nth%20node%20from%20the%20last%20of%20a%20linked%20list*%2F%0Avoid%20printNthFromLast(struct%20node*%20head%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20len%20%3D%200%2C%20i%3B%0A%20%20%20%20struct%20node%20*temp%20%3D%20head%3B%0A%20%0A%20%20%20%20%2F%2F%201)%20count%20the%20number%20of%20nodes%20in%20Linked%20List%0A%20%20%20%20while%20(temp%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%20%20%20%20%20%20%20len%2B%2B%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20check%20if%20value%20of%20n%20is%20not%20more%20than%20length%20of%20the%20linked%20list%0A%20%20%20%20if%20(len%20%3C%20n)%0A%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20temp%20%3D%20head%3B%0A%20%0A%20%20%20%20%2F%2F%202)%20get%20the%20(n-len%2B1)th%20node%20from%20the%20begining%0A%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%20len-n%2B1%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%0A%20%20%20%20printf%20(%22%25d%22%2C%20temp-%3Edata)%3B%0A%20%0A%20%20%20%20return%3B%0A%7D%0A%20%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%2F*%20allocate%20node%20*%2F%0A%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%0A%20%20%2F%2F%20create%20linked%2035-%3E15-%3E4-%3E20%0A%20%20push(%26head%2C%2020)%3B%0A%20%20push(%26head%2C%204)%3B%0A%20%20push(%26head%2C%2015)%3B%0A%20%20push(%26head%2C%2035)%3B%0A%20%0A%20%20printNthFromLast(head%2C%205)%3B%0A%20%20return%200%3B%20%0A%7D” message=”” highlight=”” provider=”manual”/]

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:

[pastacode lang=”c” manual=”void%20printNthFromLast(struct%20node*%20head%2C%20int%20n)%20%0A%7B%0A%20%20%20%20static%20int%20i%20%3D%200%3B%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20return%3B%0A%20%20%20%20printNthFromLast(head-%3Enext%2C%20n)%3B%0A%20%20%20%20if%20(%2B%2Bi%20%3D%3D%20n)%0A%20%20%20%20%20%20%20printf(%22%25d%22%2C%20head-%3Edata)%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

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:

[pastacode lang=”python” manual=”%23%20Python%20program%20to%20find%20n’th%20node%20from%20end%20using%20slow%0A%23%20and%20fast%20pointer%0A%20%0A%23%20Node%20class%20%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20initialize%20the%20node%20object%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%0Aclass%20LinkedList%3A%0A%20%0A%20%20%20%20%23%20Function%20to%20initialize%20head%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%20%20%20%23%20Function%20to%20insert%20a%20new%20node%20at%20the%20beginning%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%20%20%20def%20printNthFromLast(self%2C%20n)%3A%0A%20%20%20%20%20%20%20%20main_ptr%20%3D%20self.head%0A%20%20%20%20%20%20%20%20ref_ptr%20%3D%20self.head%20%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20count%20%20%3D%200%0A%20%20%20%20%20%20%20%20if(self.head%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20while(count%20%3C%20n%20)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if(ref_ptr%20is%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20%22%25d%20is%20greater%20than%20the%20no.%20pf%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nodes%20in%20list%22%20%25(n)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ref_ptr%20%3D%20ref_ptr.next%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%20%2B%3D%201%0A%20%0A%20%20%20%20%20%20%20%20while(ref_ptr%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20main_ptr%20%3D%20main_ptr.next%0A%20%20%20%20%20%20%20%20%20%20%20%20ref_ptr%20%3D%20ref_ptr.next%0A%20%0A%20%20%20%20%20%20%20%20print%20%22Node%20no.%20%25d%20from%20last%20is%20%25d%20%22%20%25(n%2C%20main_ptr.data)%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Allist%20%3D%20LinkedList()%0Allist.push(20)%0Allist.push(4)%0Allist.push(15)%0Allist.push(35)%0A%20%0Allist.printNthFromLast(4)%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)%0A” message=”” highlight=”” provider=”manual”/]

Output:

Node no. 4 from last is 35

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

[ad type=”banner”]