21 February 2010

Find kth node from the last in a singly linked list without using counter

The objective for this program is to find the kth node from the last without actually finding the size of the singly linked list.
For this problem, we need to have two pointers, lets call them FAR and NEAR. We need to initialize them by pointing them to the start. After doing that, move the FAR pointer 'k-1' times ahead. After moving that run a loop until FAR becomes null, amidst that increment both FAR and NEAR pointers.
The below picture shown is done for k=3. In step1, we are moving the pointer k-1=2 times. After that by moving parallely FAR and NEAR pointers, we can find the kth element from the last by getting the data from NEAR pointer.

The Java code for this simple program is given below. To try the below program please copy this class as well.
package dsa.linkedlist;

public class FindKthElementFromLast {
 public static void main(String args[]){
  FindKthElementFromLast kthFromLastFinder = new FindKthElementFromLast();
  SinglyLinkedList<Integer> originalList = kthFromLastFinder.getLabRatList(8);
  System.out.println("Original List : "+originalList.toString());
  kthFromLastFinder.findFromLast(originalList, 3);
 }
 
 private void findFromLast(SinglyLinkedList<Integer> singlyLinkedList, int k) {
  Node far, near;
  //initialize far and near pointers
  far = near = singlyLinkedList.start;
  //Move the far pointer k times from the starting position
  System.out.print("kth node from last for k = "+k+" is ");
  while((k--)!=0){
   far = far.next;
  }
  while(far!=null){
   near = near.next;
   far = far.next;
  }
  System.out.println(near.data);
 }

 private SinglyLinkedList<Integer> getLabRatList(int count){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=1;i<=count;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
}
//SAMPLE OUTPUT
//Original List : 1, 2, 3, 4, 5, 6, 7, 8
//kth node from last for k = 3 is 6
Cheers,
Bragaadeesh.

No comments: