力扣143：重排链表

给定一个单链表 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）