Monday, March 18, 2013

How do you find middle element of a linked list in single pass?

Hi friends, i have written the solution to the above problem in java. We use two pointers here in which first pointer will be incremented twice and another one will be incremented only once, till the first pointer reaches the end of the linked list.When the first pointer reaches the end the middle element will be the value which is pointed by the second pointer.   




import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator;
import javax.xml.soap.Node;
public class test2 {


      public static void main(String args[])
      {

            LinkedList l=new LinkedList();
            l.add(2);
            l.add(3);
            l.add(9);
            l.add(4);
           
            java.util.Iterator i1=l.iterator();
            java.util.Iterator i2=l.iterator();
           
            int i=0;
            int middle = 0;
            while(i1.hasNext())
            {
                  if(i==0)
                  {
                        i1.next();
                        i=1;
                       
                  }
                  else if(i==1)
                  {
                        if(i1.hasNext())
                        {
                             
                        i1.next();
                       
                        middle=(Integer) i2.next();
                        i=0;
                        }
                  }
            }
            System.out.println("middle"+middle);
           
           
     
      }
           
            }

Thank you.