PTA重排链表

链表是计算机科学中常用的数据结构，它是一个由一系列节点组成的集合，每个节点都包含了要存储的数据和指向下一个节点的指针。在某些情况下，需要对链表进行重排，以便更方便地访问或更有效地执行某些操作。PTA重排链表，就是指一种常见的链表重排问题，其中 PTA 是指 PAT（浙江大学程序设计能力考试）。

为什么要重排链表？

链表是一种非常有用的数据结构，但在某些情况下，需要对其进行重排以优化其性能。例如，在进行搜索或排序操作时，链表的顺序可能是关键因素。此外，在实际应用中，当需要访问链表的部分元素时，通过重新排列元素的顺序可以更快地找到所需的节点。因此，重排链表可以提高程序的效率和可读性。

如何重排链表？

每种链表重排问题都有不同的解决方案。对于PTA重排链表问题，其基本思想是将链表拆分为两个部分，并将第二个部分的节点按照从最后一个到第一个的顺序插入到第一个部分中，然后交错合并两个部分。这种方法可以通过迭代或递归实现，并且可以在常量级的空间内完成。

具体来说，可以按照以下步骤进行PTA重排链表操作：

1.将链表拆分为两个部分。可以使用一快一慢两个指针来实现这一步骤，快指针每次移动两个节点，而慢指针只在每次移动一个节点。当快指针到达链表末尾时，慢指针所在的位置就是链表的中间节点。

2.将第二个部分的节点反转。可以使用迭代或递归的方式实现。迭代方式可以使用三个指针来实现，依次反转指针的方向。递归方式则可以通过递归反转链表来实现。

3.将第二个部分的节点按照从最后一个到第一个的顺序插入到第一个部分中。可以使用一快一慢两个指针来实现这一步骤，慢指针来维护插入的位置，快指针指向第二个部分的第一个节点。然后将快指针指向的节点插入到慢指针的位置，再移动快指针和慢指针，直到第二个部分的节点插入完毕。

4.交错合并两个部分。可以使用一快一慢两个指针来依次交错将两个部分的节点合并。具体来说，慢指针指向第一个部分的第一个节点，而快指针则指向第二个部分的第一个节点。然后将快指针指向的节点插入到慢指针之后的位置，再交替移动两个指针，直到第二个部分的最后一个节点插入完毕。

如何通过代码实现？

下面是使用C++语言实现PTA重排链表的示例代码，实现过程中使用了迭代方式逆转链表：

```c++

#include

using namespace std;

struct ListNode {

int val;

ListNode* next;

ListNode(int x) : val(x), next(NULL) {}

};

class Solution {

public:

void reorderList(ListNode* head) {

if (!head || !head->next)

return;

// 将链表拆分为两个部分

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

}

ListNode* second = slow->next;

slow->next = NULL;

// 反转第二个部分

ListNode* pre = NULL;

while (second) {

ListNode* nxt = second->next;

second->next = pre;

pre = second;

second = nxt;

}

// 将第二个部分的节点插入到第一个部分中

ListNode* p1 = head;

ListNode* p2 = pre;

while (p1 && p2) {

ListNode* nxt1 = p1->next;

ListNode* nxt2 = p2->next;

p1->next = p2;

p2->next = nxt1;

p1 = nxt1;

p2 = nxt2;

}

}

};

```

以上代码中，Solution类的reorderList函数就是进行PTA重排链表操作的主要函数。首先使用快慢指针将链表拆分为两个部分，然后使用迭代方式逆转第二个部分，再将第二个部分的节点按照从最后一个到第一个的顺序插入到第一个部分中，最后交错合并两个部分的节点。