【牛客题霸题解】重排链表（待更新java、py）

前置题目；
NC78反转链表
NC33合并两个有序链表
题目思路：
1、找到链表的中间结点
2、把后半部分链表反转
3、合并两个链表
对于第一步操作，我们设置两个指针快指针每次走两步，慢指针每次走一步，快指针走到空结点的时候慢指针就在链表的中间结点了。
第二步反转操作参考NC78反转链表
第三步合并操作参考NC33合并两个有序链表
c++

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* Pre = NULL;
        ListNode* Now = pHead;
        ListNode* Next = NULL;
        while(Now!=NULL)
        {
            Next = Now->next;
            Now->next = Pre;
            Pre = Now;
            Now = Next;
        }
        pHead = Pre;
        return pHead;
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = l1;
        ListNode* now = l1;
        l1 = l1->next;
        int t = 2;
        while( l1!=NULL || l2!=NULL )
        {
            if(l2==NULL || (l1!=NULL&&t==1) )//用l1的结点
            {
                now->next = l1;
                l1 = l1->next;
                t = 2;
            }
            else
            {
                now->next = l2;
                l2 = l2->next;
                t = 1;
            }
            now = now->next;

        }
        return head;
    }
    void reorderList(ListNode *head) {
        if(head == NULL){return;}
        //找出链表的中间结点
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next!=NULL&&fast->next->next!=NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* headmid = slow->next;
        slow->next = NULL;
        headmid = ReverseList(headmid);
        head = mergeTwoLists(head,headmid);
    }
};

java

python