企业官网建设流程全解析

链表的交换要注意 “链表不断链”。前驱和后继都要连着

迭代法（必学死磕！O (n) 时间，O (1) 空间）

1. 为什么必须用虚拟头节点？

因为交换后链表的头节点会变！ 比如示例 1 中，原来的头是 1，交换后头变成了 2。如果不用虚拟头，你需要单独处理头节点的情况，非常容易出错。 用虚拟头节点的好处：统一所有节点的交换逻辑，不用单独处理头节点。

2. 核心思想

我们用一个指针p永远指向当前要交换的两个节点的前一个节点。 每次只需要交换p后面的两个节点node1和node2，然后把p移动到node1，继续交换下一对，直到没有足够的节点可以交换为止。

3. 交换的固定 3 步（顺序绝对不能乱！）

交换前的结构：p→ node1 → node2 → 后面的节点我们要变成：p→ node2 → node1 → 后面的节点

必须严格按照以下 3 步执行，否则会断链：

1. p->next = node2：让 p 直接指向 node2
2. node1->next = node2->next：让 node1 指向 node2 后面的节点（先把后面的链表接住，不然会丢）
3. node2->next = node1：让 node2 指向 node1

⚠️ 关键：第二步必须先做，先把 node2 后面的链表存到 node1 的 next 里，不然 node2 的 next 改了之后，后面的链表就找不到了

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode *head2;//中间量用来交换 ListNode *dhead = new ListNode(-1,head); ListNode *p = dhead; //要保证后面至少有两个节点可以交换 while(p->next->next!=nullptr && p->next!=nullptr){ ListNode* node1 = p->next;//原来的节点1 ListNode* node2 = p->next->next;//原来的节点2 p->next = node2;//p的后继为2节点 node1->next=node2->next;//1节点的下一个应该为原来2节点的下一个 node2->next=node1;//2节点的下一个应为1一节点 // prev-> 1 ->2 ->3 //交换后： prev->2->1->3 //p一开始为head的前驱，只要再让它等于node1，就可以表示是3的前驱了。 p = node1; } return dhead->next; } };