We need to find nth node from the end
of the list.
 |
| nth node from end of linked list
Logic 1: Brute Force Approach
we take one node and count the
remaining nodes from it. If it is n then
it is desired node otherwise we point
to next node .
Here we are maintaning two
pointers.Thats why it has o(n^2) complexity.
time: O(n^2)
space: O(1)
Logic2: By Length
Here we first find the lenght of linked
list say l.
Then we get node l-n+1, which is nth
node from last node.
1->2->3->4->5
length is 5.
let say we want 2nd node from last.
So, move_dist=5-2+1=4
so we move upto 4th node from head and
after moving , wtever node comes is
our desired node(here 4)
Time: O(n)
Space O(1)
Logic 3:By Two Pointers
we point two pointer to head say t1 and
t2. Now we move t1 pointer
upto n move. t2 remains freeze.
after t1’s move completed, we move both
pointer until t1!=NULL.
t2 will point the desired node..
time: O(n)
space O(1)
best complexity:
order Complexity O(n)
space Complexity O(1)
|
