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

这道链表重排序问题可以拆分为以下三个小问题：

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 || !head->next) return;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast && fast->next) {
            slow=slow->next;
            fast=fast->next->next;
        }
   
        ListNode* mid = slow->next;
        slow->next=NULL;
        ListNode * prev = NULL;
        ListNode * next = NULL;
        while(mid) {
            next=mid->next;
            mid->next=prev;
            prev=mid;
            mid=next;  
        }
   
        mid = prev;
   
        ListNode* snext;
        while(head && mid) {
            next=head->next;
            head->next=mid;
            snext=mid->next;
            mid->next=next;
            mid=snext;
            head=next;
        }  
    }
   };