13. Reorder List

Reorder List

Given a singly linked list L: L→L→…→L→L, reorder it to: L→L→L→L→L→L→…

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

说明：分三步，1。从中间分开，成两部分。2，后半部分链表逆置。3.插入合并。

/**

 * 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 *p1, *p2, *p3, *head2;

        p1 = p2 = head;

        while(p2->next && p2->next->next) {

            p1 = p1->next;

            p2 = p2->next->next;

        }

        head2 = p1->next; p1 = p1->next = NULL;

        p2 = head2;

        while(p2) {

            p3 = p2->next;

            p2->next = p1;

            p1 = p2;

            p2 = p3;

        }

        head2 = p1; p1 = head;

        while(head2 && p1) {

            p2 = head2->next;

            head2->next = p1->next;

            p1->next = head2;

            head2 = p2;

            p1 = p1->next->next;

        }

    }

};