思路
快慢指针找到链表的中间结点，将原链表分为两部分，之后将链表的后半部分逆置，之后合并两个单链表，注意：一定要判定头部是否为空！
代码
class Solution {
public:void reorderList(ListNode *head) {if (head != NULL){//快慢指针求中间结点ListNode *slow = head;ListNode *fast = head;while (fast->next != NULL && fast->next->next != NULL){slow = slow->next;fast = fast->next->next;}//将链表的后面部分逆置fast = slow->next;slow->next = NULL;ListNode *new_head = new ListNode(0);while (fast){ListNode *tmp = fast->next;fast->next = new_head->next;new_head->next = fast;fast = tmp;}//合并ListNode *p = head;ListNode *q = new_head->next;while (q != NULL){ListNode *n = q->next;q->next = p->next;p->next = q;p = p->next->next;q = n;}}}
};