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.

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

 
class Solution {
public:
     ListNode *reverse( ListNode *list)
     {
          ListNode *prev = NULL;
          while(list) {
               ListNode *tmp = list->next;
               list->next = prev;
               prev = list;
               list = tmp;
          }
          
          return prev;
     } 
     
     void reorderList(ListNode *head) {
        if (!head) return;
        
        ListNode *fast = head;
        ListNode *slow = head;
        
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        } 
        
        ListNode *second = slow->next;
        slow->next = NULL;
        
        ListNode *reversed = reverse(second);
        
        ListNode dummy(0);
        ListNode *p = &dummy;
        while(head || reversed)
        {
            if (head) {
                p->next = head;
                p = p->next;
                head = head->next;
            }
            if (reversed) {
                p->next = reversed;
                p = p->next;
                reversed = reversed->next;
            }
            
        }
    }
};

 
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    void reorderList(ListNode *head) {
        if (!head) return;
        stack<ListNode *> st;
        
        ListNode *p = head;
        int count = 0;
        while(p) {
            st.push(p);
            p = p->next;
            count++;
        }
        p = head;
        count /= 2;
        while(count >0)
        {
            ListNode *next = p->next;
            p->next = st.top();
            st.pop();
            p->next->next = next;
            p = next;
            count--;
        }
        p->next = NULL;
    }
};