关注我，分享高质量每日一题题解~

b站同名账号分享力扣杯历届真题视频题解，也欢迎大家提出宝贵意见！

思路：线性表

• 因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。
• 因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。
• 本方法的空间复杂度达到了 $O(n)$，若想不利用额外空间，可以先找到链表中点，将右半部分反转，再将左半部分和右半部分合并即可。

代码（C++）

class Solution {
public:
    void reorderList(ListNode *head) {
        if (head == nullptr) {
            return;
        }
        vector<ListNode *> vec;
        ListNode *node = head;
        while (node != nullptr) {
            vec.emplace_back(node);
            node = node->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;
    }
};

时间复杂度：$O(n)$