title: Merging two halves of a singly linked list
body: <p><br>
  In a written test I came across a question which reads as follows:<br><br></p>
  
  <p>We are given an integer linked list of which both first half and second half are sorted independently. Write a function to merge the two parts to create one single sorted linked list. <br></p>
  
  <p><b>Constraint: do not use any extra space.</b><br><br></p>
  
  <p>Test Cases and output:<br> <b>Input List1 :</b><br>4->5->6->7->1->2->3; <br> <b>Output :</b><br> 1->2->3->4->5->6->7 <br><br><b>Input 2: </b><br> 5->6->7->8->1->2->3->4; <br> <b>Output 2 :</b><br> 1->2->3->4->5->6->7->8<br></p>
  
  <p>What I can think of is by using two pointers: one for the first half traversal and one for the second half traversal. Using them I can traverse from head to middle (using 1st pointer) and from middle to last (using 2nd Pointer). While traversing both parts simultaneously, I can compare values and swap when needed. <br><br>
  But this solution employs use of two pointers which consumes memory.<br><br></p>
  
  <p>Can it be done without using any memory? <br><br>
  As it was a written test, I cannot ask for clarifications. <br>
  Assistance is appreciated. Thanks.</p>