143. 重排链表
难度中等279
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
/*** 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) return;ListNode* slow = head;ListNode* fast = head;while(fast and fast->next){slow =slow->next;fast = fast ->next->next;} //断开ListNode* p = slow->next;slow->next = nullptr;slow = p;p = nullptr;while(slow!=nullptr){auto node = slow->next;slow->next = p;p = slow;slow = node;}auto q = head;while(p){auto node = p->next;p->next = q->next;q->next = p;q = p->next;p = node; }}
};