重排链表(快慢指针/指针反序)

题目： 参考：https://leetcode-cn.com/problems/reorder-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-34/ 给定一个单链表 L ： L 0 → L 1 → … → L n − 1 → L n ， L：L_0→L_1→…→L_{n-1}→L_n ， L：L0​→L1​→…→Ln−1​→Ln​， 将其重新排列后变为： L 0 → L n → L 1 → L n − 1 → L 2 → L n − 2 → … L_0→L_n→L_1→L_{n-1}→L_2→L{n-2}→… L0​→Ln​→L1​→Ln−1​→L2​→Ln−2→…

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	/*
	*先通过快慢指针，将链表划分为前后部分，后部分倒序
	*再将这2部分合并即可
	*/
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
            return;
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *newhead = slow->next;
        slow->next = nullptr;//
        newhead = reverselist(newhead);
        while(newhead != nullptr) {
            ListNode *tmp = newhead->next;
            newhead->next = head->next;
            head->next = newhead;
            head = newhead->next;
            newhead = tmp;
        }

    }
    ListNode* reverselist(ListNode *head) {
        if(head == nullptr) return head;
        ListNode *pre = head;
        head = head->next;
        pre->next = nullptr;//
        while(head != nullptr) {
            ListNode *tmp = head->next;
            head->next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
};