Problem of the Day
A new programming or logic puzzle every Mon-Fri

Given a linked list with at least 3 nodes, return the middle element of that list in a single pass through. You're not allowed to reiterate through the list. Bonus points for not copying all the elements of the list to an array.

Comments:

• pypy - 10 years, 6 months ago

  Python 2.7. Same algorithm can be used to check for loops in a linked list I think. Just add a check to see if slow == fast in the loop.

  def getMiddle(links):
      fast = links
      slow = links
      while fast is not None:
          fast = fast.next
          if fast is not None: 
              fast = fast.next
          else: 
              return slow
          slow = slow.next
      return slow
  

  reply permalink

• Max Burstein - 10 years, 6 months ago

  Nicely done

  reply permalink

• Rawin - 10 years, 6 months ago

  I love this one!

  reply permalink

• Nick Krichevsky - 10 years, 6 months ago

  Got it in C++. I think mine might be a bit strange, since I had to add an exception for the length being even. If the length is even, there is technically no middle of the list.

  #include <iostream>
  #include <ctime>
  class Node{
      public:
          Node(){};
          Node * next;
  };
  int main(){
      srand(time(NULL));
      Node * first = new Node();
      Node * point = first;
      for (int i=0; i<rand()%50+3; i++){
          point->next = new Node();
          point = point->next;
      }
      int i=1;
      for (point=first; point!=NULL; point=point->next){
          i++;
      }
      std::cout<<i<<std::endl;
      if (i%2==0){
          std::cout<<"middle is between "<<i/2<<" and "<<i/2+1<<std::endl;
      }
      else{
          std::cout<<"middle is at "<<i/2+1<<std::endl;
      }
      return 0;
  }
  

  reply permalink

• Max Burstein - 10 years, 6 months ago

  Very true. Good simple code and handles all cases. I like it.

  reply permalink