力扣HOT100（30）两两交换链表中的节点

链表的交换要注意 “链表不断链”。前驱和后继都要连着迭代法必学死磕O (n) 时间O (1) 空间1. 为什么必须用虚拟头节点因为交换后链表的头节点会变 比如示例 1 中原来的头是 1交换后头变成了 2。如果不用虚拟头你需要单独处理头节点的情况非常容易出错。 用虚拟头节点的好处统一所有节点的交换逻辑不用单独处理头节点。2. 核心思想我们用一个指针p永远指向当前要交换的两个节点的前一个节点。 每次只需要交换p后面的两个节点node1和node2然后把p移动到node1继续交换下一对直到没有足够的节点可以交换为止。3. 交换的固定 3 步顺序绝对不能乱交换前的结构p→ node1 → node2 → 后面的节点我们要变成p→ node2 → node1 → 后面的节点必须严格按照以下 3 步执行否则会断链p-next node2让 p 直接指向 node2node1-next node2-next让 node1 指向 node2 后面的节点先把后面的链表接住不然会丢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-nextnode2-next;//1节点的下一个应该为原来2节点的下一个 node2-nextnode1;//2节点的下一个应为1一节点 // prev- 1 -2 -3 //交换后 prev-2-1-3 //p一开始为head的前驱只要再让它等于node1就可以表示是3的前驱了。 p node1; } return dhead-next; } };