重排链表

🤯好难

不过没关系，还是刚出来了

其实方法是不难想到的，但是实现起来却比较麻烦，其中涉及有：

1. 快慢指针（注意循环条件）；
2. 链表反转（熟练运用中间变量）；
3. 链表合并（哑节点很香）

嘻嘻，就4这样de^^

//
// Created by jt on 2020/8/8.
//
#include 
using namespace std;
/**
 * 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 || !head->next || !head->next->next) return;
        // 1\. 用快慢指针找中间节点
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 2\. 对slow后面的部分逆序
        fast = slow->next;
        slow->next = nullptr;
        slow = nullptr;
        while (fast) {
            ListNode *temp = fast->next;
            fast->next = slow;
            slow = fast;
            fast = temp;
        }
        // 3\. 重新合并链表
        ListNode dummy(0);                   // 哑节点
        ListNode *r = &dummy;
        ListNode *p, *q;                     // 记录第一个节点
        while (slow && head) {
            p = head;
            q = slow;
            slow = slow->next;
            head = head->next;
            r->next = p;
            r = p;
            r->next = q;
            r = q;
        }
        if(slow) r->next = slow;
        if(head) r->next = head;
        head = dummy.next;
    }
};