title: Array folding into a single element
body: <p>This is an interview question not a homework.</p>
  
  <p>Given a array of 1 to 2 ^N. For eg: 1 2 3 4 5 6 7 8 (2^3) .Imagine this array is written on a paper, we need to fold this into half, so that the left half will be mirrored and then moved underneath the right half like this</p>
  
  <pre><code>1 2 3 4 5 6 7 8
   left  |  right
   half  |  half
  </code></pre>
  
  <p>becomes</p>
  
  <pre><code>5 6 7 8
  4 3 2 1
  </code></pre>
  
  <p>And the next fold we take the <em>right</em> half instead, mirroring it and moving it below the left half, </p>
  
  <pre><code> 5 6 
   4 3 
   8 7
   1 2 
  </code></pre>
  
  <p>The paper has to be folded, changing direction (left-vs-right) each time, until we have all the elements in the single column like this </p>
  
  <pre><code> 6
   3
   7 
   2
   5
   4
   8 
   1 
  </code></pre>
  
  <p>My solution, 
  First step :
  Create a linked list for the second half of the original array, and reverse the first half and connect it with head pointers,</p>
  
  <pre><code>5 6 7 8 
  | | | |
  4 3 2 1
  </code></pre>
  
  <p>And store the head pointers of linked list in an array called headarray</p>
  
  <p>Iteratively : </p>
  
  <p>fold the head array, for each fold either the first half and second half headers will be linked. Delete the head pointers from the headarray once it is linked.</p>
  
  <p>Continue until w have a single head pointer in the head array. </p>
  
  <p>But the interviewer asked me to solve it in stack. Could anyone help in getting this solved in stack and also point out if have done any mistake in my solution. Thanks in advance.  </p>