/**

 * 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;

        // two pointers split the list

        // 快慢指针，快指针到尾时，慢指针在前list尾部

        // example: 1->2->3->4->5 fast=5,slow=3, 1->2->3 & 4->5

        // example: 1->2->3->4    fast=3,slow=2, 1->2    & 3->4

        ListNode *slow = head, *fast = head;

        while(fast->next !=NULL && fast->next->next !=NULL){

            slow = slow ->next;

            fast = fast->next->next;

        }

        ListNode *head1 = head;

        // reverse the second list(with large numbers)

        // 翻转第二个链表

        ListNode *head2 = reverseList(slow->next);

        slow->next = NULL;

        while(head2!=NULL){             // list1 size >= list2 size

            ListNode *next1 = head1->next;

            ListNode *next2 = head2->next;

            head1->next = head2;

            head2->next = next1;

            head1 = next1;

            head2 = next2;

        }

        if(head1!=NULL){

            head1->next = NULL;

        }

    }

    // reverse list

    ListNode *reverseList(ListNode *head){

        if(head==NULL || head->next ==NULL) return head;

        ListNode * new_head = NULL;

        while(head!=NULL){

            ListNode *pNext = head->next;

            head->next = new_head;

            new_head = head;

            head = pNext;

        }

        return new_head;

    }

};

/**

 * 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) {

        stack<ListNode* > nodestack;

        int length=;

        // 计算链表长度，结点压入stack

        ListNode *temp = head;

        while(temp){

            length++;

            nodestack.push(temp);

            temp = temp->next;

        }

        // 栈弹出，连接链表

        temp = head;

        int cnt = length/;

        while(cnt){

            ListNode *head2 = nodestack.top();

            nodestack.pop();

            ListNode *headNext = temp->next;

            temp->next =head2;

            head2->next = headNext;

            temp = headNext;

            cnt--;

        }

        // 总数为odd，temp指向末尾元素

        // 总数为even，temp会和前元素重复，此处删除

        if(length%){

            temp->next = NULL;

        }else{

            temp = NULL;

        }

    }

};