[数据结构与算法]力扣-143题 重排链表（C++）- 链表的操作

题目链接：https://leetcode-cn.com/problems/reorder-list/
题目如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head||!head->next) return;

        //找链表的中间节点，最终为slow，若1234，则slow在2上
        auto fast=head,slow=head;
        while(fast->next&&fast->next->next){
            slow=slow->next;
            fast=fast->next->next;
        }

        //交换后半链表
        cout<<slow->val<<endl;
        auto temp=slow->next;
        slow->next=nullptr;
        auto p2=reverse(temp);

        //将p1、p2合并到一个链表中
        auto p1=head;
        ListNode* temp1,*temp2;
        while(p1&&p2){
            temp1=p1->next;
            temp2=p2->next;

            p1->next=p2;
            p1=temp1;

            p2->next=p1;
            p2=temp2;
        }
    }

    ListNode* reverse(ListNode* head){
        ListNode* pre=nullptr;
        ListNode* cur=head;

        while(cur){
            auto temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }

        return pre;
    }
};