[LeetCode] Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution:

/**
 * 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 || head -> next == NULL) 
        return;
      ListNode *fast = head, *slow = head, *tmp1 = NULL, *tmp2 = NULL, *ansHead = NULL, *ansEnd = NULL;
        while(fast -> next != NULL)
      {
        fast = fast -> next;
        if(fast -> next == NULL)
        {
          //reach the end
          break;
        }
        else
        {
          fast = fast -> next;
          slow = slow -> next;
        }
      } 
        
      ListNode *list2start = slow -> next;
      slow -> next = NULL;
      tmp1 = list2start -> next;
      list2start -> next = NULL;
      while(tmp1 != NULL)
      {
        tmp2 = tmp1 -> next;
        tmp1 -> next = list2start;
        list2start = tmp1;
        tmp1 = tmp2;
      }
      tmp1 = head -> next;
      tmp2 = list2start;
      ansHead = head;
      ansEnd = head;
      while(tmp1 != NULL || tmp2 != NULL)
      {
        if(tmp2 != NULL)
        {
          ansEnd -> next = tmp2;
          tmp2 = tmp2 -> next;
          ansEnd = ansEnd -> next;
        }
        if(tmp1 != NULL)
        {
          ansEnd -> next = tmp1;
          tmp1 = tmp1 ->next;
          ansEnd = ansEnd -> next;
        }
      }
      head = ansHead;
      return;
    }
};