题解 | #重排链表#

无语，今晚牛客是不是抽风了

/**
 * 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 == nullptr || head->next == nullptr) {
        return ;
      }
      
      //  利用快慢指针移动到中间，翻转后半段链表，然后合并两段链表
      ListNode *fast, *slow;
      fast = slow = head;
      
      //  slow 走到中间位置
      while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
      }
      
      
      ListNode *pre = nullptr, *cur = slow->next, *nex = slow->next->next;
      
      //  断开链接
      slow->next = nullptr;
      
      while (nex) {
        cur->next = pre;
        pre = cur;
        cur = nex;
        nex = nex->next;
      }
      
      cur->next = pre;
      
      ListNode *head1 = head, *head2 = cur;
      
      while (head1 && head2) {
        ListNode *nex1 = head1->next;
        ListNode *nex2 = head2->next;
        head1->next = head2;
        head2->next = nex1;
        head1 = nex1;
        head2 = nex2;
      }
    }
};