题解 | #重排链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
    ListNode* reverse(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        auto newHead = reverse(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
    ListNode* merge(ListNode* h1, ListNode* h2) {
        ListNode* r = h1;
        int cnt = 1;
        while ((h1 != h2) && h1 && h2) {
            if (cnt & 1) {
                ListNode* next = h1->next;
                h1->next = h2;
                h1 = next;
            } else {
                ListNode* next = h2->next;
                h2->next = h1;
                h2 = next;
            }
            cnt++;
        }
        return r;
    }
    void reorderList(ListNode* head) {
        ListNode* fast = head;
        ListNode* low = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            low = low->next;
        }
        ListNode* mid = low;
        mid = reverse(mid);
        merge(head, mid);


    }
};

我考虑的有点复杂了感觉