给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

思想：先求得链表的中间结点，然后按照中间结点分为两个链表。将第二个链表进行逆转，然后和第一个链表进行合并。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///找中间结点struct ListNode *middleNode(struct ListNode* head){struct ListNode *fast=head;struct ListNode *slow=head;while(fast != NULL && fast->next !=NULL){fast=fast->next->next;slow=slow->next;}return slow;}//逆转后半部分struct ListNode *reverse(struct ListNode *head){struct ListNode *pre=NULL;struct ListNode *p=head;struct ListNode *r;while(p!=NULL){r=p->next;p->next=pre;pre=p;p=r;}return pre;}//合并两个链表void merge(struct ListNode*L1,struct ListNode*L2){struct ListNode *p1;struct ListNode *p2;while(L1 != NULL && L2 != NULL){p1=L1->next;p2=L2->next;L1->next=L2;L1=p1;L2->next=L1;L2=p2;}}
void reorderList(struct ListNode* head) {if(head==NULL){return;}struct ListNode *mid=middleNode(head);struct ListNode *L1=head;struct ListNode *L2=mid->next;mid->next=NULL;L2=reverse(L2);merge(L1,L2);
}

时间复杂度O（n）；空间复杂度O（n）