Saturday, October 27, 2012

Singly Linked List: Nth Node from end


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