title: Runner technique to combine two equal Linked Lists of general size
body: <p>2
  So, I am facing a doubt here.</p>
  
  <p>I was reading the book Cracking the coding Interview. The following text is written over there.</p>
  
  <p>Suppose you had a linked list a1->a2....->an->b1->b2....bn, and you want to rearrange it into a1->b1->a2->b2->.....an->bn. You don't know the length of the linked list but all you know is that it is an even number.</p>
  
  <p>(Here both the linked lists are of the same length)</p>
  
  <p>You could have one pointer p1 (fast pointer) move every two elements for every one move that p2 makes. When p1 hits the end of the linked list, p2 will be at the endpoint. Then, move p1 back to the front and begin "weaving" the elements. On each iteration, p2 selects an element and inserts it after p1.</p>
  
  <p>I don't understand how when p1 hits the end of the linked list, p2 will be at the midpoint. This is how I am imagining it if n=3 (length = 6). Each step below represents an iteration.</p>
  
  <p>I have tried with linked listed consisting of 4 elements and was successful in achieving the result. However, I can't solve for the general case, because my pointers get dangly. Would it be possible to provide code for the problem in python, I am stuck. And this is my code:</p>
  
  <pre><code>def runner_technique_ex(self, head):
      """
      Assume the length of the ll that we will run thru will be even
      :param head:
      :return:
      """
      slow = head
      fast = head.next
      while fast.next is not None:
          slow = slow.next
          fast = fast.next.next
  
      fast = head
      slow = slow.next
      while slow.next is not None:
          tempSlow = slow
          tempFast = fast.next
          fast.next = tempSlow
          slow = slow.next
          tempSlow.next = tempFast
          tempFast.next = slow
  </code></pre>