官方题解https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/
/** * 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 || !head->next) return; //找中间结点 ListNode* mid=FindMid(head); //中间结点之后翻转，成为新的链表 ListNode *l1=head, *l2=mid->next; mid->next=NULL; l2=reverse(l2); //两个链表合并 merge(l1,l2); } ListNode* FindMid(ListNode* head){ ListNode *fast=head, *slow=head; while(fast && fast->next){ fast=fast->next->next; slow=slow->next; } return slow; } ListNode* reverse(ListNode* head){ ListNode *pre=NULL, *p=head, *next=NULL; while(p){ next=p->next; p->next=pre; pre=p; p=next; } return pre; } ListNode* merge(ListNode* h1, ListNode* h2){ ListNode *h1_next=NULL, *h2_next=NULL; while(h1 && h2){ h1_next=h1->next; h2_next=h2->next; h1->next=h2; h2->next=h1_next; h1=h1_next; h2=h2_next; } return h1; } };例子：
