Implement an algorithm to find the nth to last element of a singly linked list.
Approach:
lets assume n = 3;
declare 2 ptrs, prev and current which point to the head of the linked list.
advance current by n (3) positions.
then advance both prev and current pointers one at a time till current becomes null.
At this point prev is the nth node from end of the linked list.
Input/Output:
51 -> 70 -> 74 -> 32 -> 10 -> 90 -> 18 -> 21 -> 30 -> null
3 node from end: 18
7 node from end: 74
9 node from end: 51
10 node from end is null
19 -> 16 -> 15 -> null
3 node from end: 19
7 node from end is null
9 node from end is null
10 node from end is null
Time complexity: O(n) - where n is the size of the singly linked list.
No comments:
Post a Comment