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:
I agree with your solutions
You're the first one to comment.. thnks :)
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
Hi,
what happens if doubleJump is null?
@bonnahu : That is taken care of in this line while(doubleJump.next!=null && doubleJump.next.next!=null)
Post a Comment