NC2 重排链_要求使用原地算法，不能只改变节点内部的值

描述

将给定的单链表$L：L_0\to L_1\to \dots \to L_{n-1}\to L_n$
重新排序为：$L_0\to L_n\to L_1\to L_{n-1}\to L_2\to L_{n-2}\to \dots$
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
数据范围：链表长度0≤n≤20000 ，链表中每个节点的值满足0≤val≤1000
要求：空间复杂度 O(n) 并在链表上进行操作而不新建链表，时间复杂度 O(n)
进阶：空间复杂度 O(1) ， 时间复杂度 O(n)

示例1
输入：{1,2,3,4}
返回值：{1,4,2,3}
说明：给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 1

示例2
输入：{1,2,3,4,5}
返回值：{1,5,2,4,3}
说明：给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出

示例3
输入：{}
返回值：{}

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if(head==nullptr||head->next==nullptr)
            return;
        vector<ListNode*> vec;
        ListNode *p=head;
        while(p){
            vec.push_back(p);
            p=p->next;
        }
        int i=0,j=vec.size()-1;
        while(i<j){
            vec[i]->next=vec[j];
            i++;
            if(i==j)
                break;
            vec[j]->next=vec[i];
            j--;
        }
        vec[i]->next=nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31