C++实现LeetCode(143.链表重排序)

对于C++实现LeetCode题目，一般需要注意以下几个方面：

1.理解题目，找出其中的规律和特点。
2.选择适当的数据结构和算法，实现解题思路。
3.编写代码实现解题思路。
4.提交代码并检查题目结果。

下面我们来详细讲解如何用C++实现LeetCode（143.链表重排序）的完整攻略。首先，我们可以查看题目描述：

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

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

从题目描述中可以看出，要求我们重新排列链表，将链表的头节点与尾节点相连接，依次从头结点和尾节点中取出节点，依次排列，直到中间节点为止。 因此，我们需要将链表分为两个部分，一部分是头节点和中间节点之前的节点，另一部分是中间节点和尾节点之间的节点，将这两个部分分别转化为顺序表，然后依次组合就可以得到最终结果。

接下来，我们可以来看看实现过程：

1.读入链表，并将节点存入数组中。

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        ListNode* cur = head;
        vector<ListNode*> vec;  // 存储所有节点
        while (cur) {
            vec.emplace_back(cur);
            cur = cur->next;
        }
        int n = vec.size();

2.将链表分为两个顺序表，并翻转后一个顺序表。

        for (int i = 0; i < n / 2; ++i) {
            vec[i]->next = vec[n - i - 1];
            vec[n - i - 1]->next = vec[i + 1];
        }
        vec[n / 2]->next = nullptr;
        ListNode* tail = vec[n / 2 + 1];
        reverse(vec.begin() + n / 2 + 1, vec.end());

3.将两个顺序表依次合并。

        cur = head;
        for (int i = 0; i < n; ++i) {
            ListNode* t = vec[i];
            if (cur == tail) break;
            t->next = cur->next;
            cur->next = t;
            cur = t->next;
        }
    }
};

接下来，我们来看一下示例：

示例1：

输入：1->2->3->4
输出：1->4->2->3

示例2：

输入：1->2->3->4->5
输出：1->5->2->4->3

对于示例1，我们将链表分为{1,2}和{4,3}，然后倒置后一个顺序表得到{4,3}，最后合并{1,4,2,3}，得到最终结果。

对于示例2，我们将链表分为{1,2,3}和{5,4}，然后倒置后一个顺序表得到{5,4}，最后合并{1,5,2,4,3}，得到最终结果。

最后，我们通过提交代码和检查题目结果来验证代码的正确性。