08 February 2010

Program to find center of a singly linked list in java

This is a very common data structure problem, to find the center of a singly linked list. And the following is the famous solution. I have tried to give a comprehensive code coverage for this problem. The list count can either be odd or even. If its odd, we have only one value as the center and two for even case. I have covered both in the following code. Please do take a look at the SinglyLinkedList class for this program for reference.
This is how it works, there will be two pointers, one jumping once and another one jumping twice. When the double jumper ends/terminates, the single jump fellow's data would be the center.



package dsa.linkedlist;

public class FindCenterOfAList {
 public static void main(String args[]){
  FindCenterOfAList ratList = new FindCenterOfAList();
  ratList.test(10);//TEST FOR EVEN
  ratList.test(17);//TEST FOR ODD
  ratList.test(1);//TEST FOR SINGLE
  ratList.test(0);//TEST FOR ZERO OR LESS
 }
 
 public int[] getMidItem(SinglyLinkedList<Integer> listToCheck){
  Node<Integer> singleJump = listToCheck.start;
  Node<Integer> doubleJump = listToCheck.start;
  
  while(doubleJump.next!=null && doubleJump.next.next!=null){
   singleJump = singleJump.next;
   doubleJump = doubleJump.next.next;
  }
  
  int[] midItem = null;
  
  if(doubleJump.next == null){
   midItem = new int[1];
   midItem[0] = singleJump.data;
  }else if(doubleJump.next.next == null){
   midItem = new int[2];
   midItem[0] = singleJump.data;
   midItem[1] = singleJump.next.data;
  }
  
  return midItem;
 }
 
 private void test(int sampleSize){
  if(sampleSize<1){
   System.out.println("List is empty!");
   return;
  }
  SinglyLinkedList<Integer> randomList = giveMeAList(sampleSize);
  System.out.print("For list : ");stringify(randomList);
  int[] midItem = getMidItem(randomList);
  if(midItem.length == 1){
   System.out.println("Middle Item : "+midItem[0]);
  }else if(midItem.length == 2){
   System.out.println("Middle Items : "+midItem[0]+", "+midItem[1]);
  }
  System.out.println();
  
 }
 
 private SinglyLinkedList<Integer> giveMeAList(int length){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=1;i<=length;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
 
 private void stringify(SinglyLinkedList<Integer> ratList) {
  for(int i=0;i<ratList.size;i++){
   System.out.print(ratList.getNodeAt(i).data+" ");
  }
  System.out.println();
 }
}
/*
-------OUTPUT--------
For list : 1 2 3 4 5 6 7 8 9 10 
Middle Items : 5, 6

For list : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
Middle Item : 9

For list : 1 
Middle Item : 1

List is empty!
*/

Cheers,
Bragaadeesh

5 comments:

Unknown said...

I agree with your solutions

BragBoy said...

You're the first one to comment.. thnks :)

Guru said...

Good One.

It will be good if the imports are shown as not everyone knows the API. I did know there is a class called Node.!

Is it not okay if we get the size of the list and find the mid items based on index? yikes.. have to look at the API properly...

Keep writing .. :) Cheers

bonnahu said...

Hi,
what happens if doubleJump is null?

BragBoy said...

@bonnahu : That is taken care of in this line while(doubleJump.next!=null && doubleJump.next.next!=null)