Reorder List

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}.

------------------------------------ codes -------------------------------------------------------------

/**

 * 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 *v1 = head;

        ListNode *v2 = head;

        ListNode *pre = head;

        while (v2) {

            pre = v1;

            v1 = v1->next;

            v2 = v2->next;

            v2 = v2 == NULL? NULL:v2->next;

        }

        pre->next = NULL;

        ListNode *nxt;

        ListNode *cur_nlst = v1;

        ListNode *nhalf = NULL;

        while (cur_nlst) {

            nxt = cur_nlst->next;

            cur_nlst->next = nhalf;

            nhalf = cur_nlst;

            cur_nlst = nxt;

        }

        //merge head and nhalf

        ListNode* cur = head->next;

        ListNode* ncur = nhalf->next;

        ListNode* rcur = nhalf;

        head->next = nhalf;

        nhalf->next = NULL;

        ListNode* nnxt;

        while (cur && ncur) {

            nxt = cur->next;

            nnxt = ncur->next;

            rcur->next = cur;

            cur->next = ncur;

            rcur = ncur;

            ncur->next = NULL;

            cur = nxt;

            ncur = nnxt;

        }

        if (cur) {

            rcur->next = cur;

            cur->next = NULL;

        }

    }

};