nth to last node in list
Find Nth to last node in linked list, meaning find node which is n nodes away from last node list. For example,
1->2->3->4->5->null 1st node from end : 5 2nd node from end : 4 3rd node from end : 3 4th node from end : 2 5th node from end : 1
Brute force solution will be to scan the entire list, find number of nodes (length), and then find difference between length and n, and then scan length-n node from head of list. Time complexity of this is O(n) however it will require scanning list twice if we are looking at 1st node from end.
Another brute force solution which not only scans list twice in worst case, but also use O(n) space. Solution is to use a stack and push all nodes of linked lists on to it. Once, done pop n nodes from stack and the last node popped will be answer. Well stack can be simulated using recursion and it becomes implicit space complexity. Also in recursion, one need to store all nodes on stack.
Find nth to last node : Recursive impementation
Can we optimize this? Yes, we can surely do. When we need to find middle of linked list, we had two pointers, when one reached at end, other was at middle. We can use similar approach here to find nth to last node. However, moving two pointers at different speeds will not help as we are not finding exactly middle or third part or something like that. What we can do is to give one pointer a head start. And what should be that head start? It should be equal to n.(remember n is not length of list, it’s nth to last node ). Once one pointer reaches its place with head start, move both pointers with same speed, one node at a time. With head start in place, when first pointer will reach end of list, second pointer will be n nodes away from end. Return second pointer as nth to last node in linked list
Algorithm to find Nth node in linked list from end
1. Initialise two pointers, first and second to head 2. Move first pointer n nodes ahead. 3. Till first pointer reaches at end 3.a move first pointer to next 3.b move second pointer to next 4. return second pointer, that will be n nodes away from end
Complexity of finding nth node from end in singly linked list will be O(n),as brute force, however number of iterations of while look will be at max n instead of 2n in brute force solution.
Let’s take some test cases and see if all execute well. It’s not about executing test cases, but to identify test cases for your program. Here are some test cases for program to find nth node in linked list from end.
Test 1 : Head is null Test 2 : n == 0, list contains some valid nodes Test 3 : n < 0, list contains some valid nodes Test 4 : n > length of linked list Test 5 : n > 0 and n < length of linked list