学步园

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

/**
 * 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) {
        
        int len = 0;
        ListNode *tmp = head;
        while(tmp)
        {
            len++;
            tmp = tmp->next;
        }
        if(head == NULL || len <= 2)
            return;
            
        ListNode *p1 = NULL;
        ListNode *p2 = NULL;
        int j = 0;
        if(len%2 == 0)
            j = len/2 - 1;
        else
            j = len/2;
        
        tmp=head;
        for(int i=0; i<j; i++)
            tmp = tmp->next;
            
        p1 = tmp;
        p2 = tmp->next;
        ListNode *reverse = NULL;
        p1->next = NULL;
        while(p2)
        {
            ListNode *p2next = p2->next;
            ListNode *rnext = reverse;
            reverse = p2;
            p2->next = rnext;
            p2 = p2next;
        }     
        tmp = head;
        while(reverse)
        {
            ListNode *next = reverse->next;
            reverse->next = tmp->next;
            tmp->next = reverse;
            tmp = reverse->next;
            reverse = next;
        }
        return;
    }
};