Leetcode -- Reorder List

TLR

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   void reorderList(ListNode *head) {  
     if(head == NULL ) {  
       return;  
     }  
     ListNode * p = head;  
     ListNode * mover = NULL;  
     while(p != NULL && p->next != NULL && p->next->next != NULL) {  
       mover = p;  
       while(mover->next != NULL && mover->next->next != NULL) {  
         mover = mover->next;  
       }  
       ListNode * temp = p ->next;  
       p->next = mover->next;  
       mover->next = NULL;  
       p->next->next = temp;  
       p = p->next->next;  
     }  
   }  
 };  

reverse the second half of the list, then merge two lists

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   void reorderList(ListNode *head) {  
     if(head == NULL ) {  
       return;  
     }  
     ListNode * slow = head;  
     ListNode * faster = head;  
     while(faster != NULL && faster->next != NULL) {  
       slow = slow->next;  
       faster = faster->next->next;  
     }  
     ListNode * halfNodeHead = slow->next;  
     slow->next = NULL;  
     ListNode * reversed = reverseLinkedList(halfNodeHead);  
     ListNode * p = head;  
     ListNode * q = reversed;  
     while(q!= NULL) {  
       ListNode * temp = p->next;  
       p->next = q;  
       q = q->next;  
       p->next->next = temp;  
       p = p->next->next;  
     }  
   }  
   ListNode * reverseLinkedList(ListNode * head) {  
     if(head == NULL) {  
       return NULL;  
     }  
     ListNode * prev = NULL;  
     ListNode * curr = head;  
     ListNode * next = NULL;  
     while(curr != NULL) {  
       next = curr->next;  
       curr->next = prev;  
       prev = curr;  
       curr = next;  
     }  
     return prev;  
   }  
 };