kth to the last element would be at [length-k] element , if the length of a linked list.
But since length is not known, we can either use iteration or recursion.
For recursion -
To simply print the kth to the least element in singly linked list , use a counter variable which increments itself
when each time the return statement is executed during recursion.
When counter equals "k" , print the value of node at that instance .
Recursion mostly imploys counter manipulation -
public static int nthToTheLast( LinkedListNode head , int k )
{
//base case
if ( head == null )
return 0 ;
//recur to reach end of the list
int counter = nthToTheLast( head.next , int k ) + 1 ;
if( counter == k )
System.out.println(head.data);
return counter ;
}
However if the question demands to return a kth to the last "node" , since we can only return a single Object at one time, an object of
a suitable wrapper class having integer value of the counter saved can be passed on each instance of recursion as in JAVA we dont have
pointers to pass by reference , but a wrapper class can help to mimic it -
For JAVA -
public class IntWrapper()
{
public int val = 0 ;
}
public LinkListNode nthToTheLast(LinkListNode head , int k , IntWrapper counter)
{
//base case
if( head == null) return 0 ;
LinkListNode = nthToTheLast(LinkListNode head , int k , IntWrapper counter) ;
if ( ++counter.val == k )
return head ; // we have found ours kth element
return node ;
}
Also, using C++ feature of pass by reference , an allias of the counter can be manipulated without using wrapper class -
node* nthToTheLast( Node* head , int k , int& counter)
{
if( head == NULL) return NULL ; //base case
node&* result = nthToTheLast( Node* head , int k , int& counter);
if(++counter == k )
return head;
return result;
}
All recursive algos for this case are O(n) for both space and time but clean .
For O(1) space complexity , the runnining technique , using 2 pointers for linked list can be used as follows -
public static LinkListNode nthToTheLastNode( LinkListNode head , int k )
{
LinkListNode p1 = p2 = head ;
//iterate p2 n position from start , such that difference between positions of p2 and p1 is k
for( int i = 0 ; i < k - 1 ; ++i)
{
if( p2 == null ) return null ; // list is too small
p2 = p2.next ;
}
if (p2 == null ) return null ; // Error check : list is small
//now move p1 and p2 with same pace , till p2 reaches end of the list.
// at this instance , p1 will be at kth to the last node
while ( p2.next != null )
{
p2 = p2.next ;
p1 = p1.next ;
}
return p1 ;
}
