问题关键点；
startNode: 表示两个交换节点的前一个节点， 称作开始节点， 初始位置为虚拟节点；
由于两个交换节点是在变化的， 所以应该在循环中执行：
node1: 表示第一个交换节点；
node2: 第二个交换节点；
交换之前顺序： startNode , node1, node2；
交换之后顺序： startNode, node2, node1;
交换的顺序
// 交换顺序将开始节点的后一个节点 更新为 node2， 称为新的第一个节点node2;
// 将原始节点node1 的后一个节点更新为原始节点Node2的 后一个节点；
// 这里的思路是， 先假设 新的第二节点，已经产生；
// 然后更新 新的第二个节点的后一个节点；
// 将新的第一个节点的后一个节点更新为node1, 称为新的第二个节点node1;
// 将开始节点 更新为 新的第二个节点node1;
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
ListNode* startNode = dummyHead;
dummyHead->next = head;
while(startNode->next != nullptr && startNode->next->next != nullptr ){
ListNode* node1 = startNode->next;
ListNode* node2 = startNode->next->next;
// 1. 先将开始节点的后一个节点更新为 node2, 称为新的第一个节点；
startNode->next = node2;
// 2. 将原始节点Node1的后一个节点更新为 原始node2 的后一个节点；
// 这里的思路是， 先更新了 新的第二个节点 的后一个节点，
// 代表了 Node1 将 成为新的 第二个节点；
node1->next = node2->next;
//3. 将新的第一节点node2 后面的一个节点更新为node1, 成为新的第二个节点；
node2->next = node1;
// 将 开始节点 更新为 新的第二个节点；
startNode = node1;
}
return dummyHead->next;
}
};
2.删除倒数 第 N 个节点；
思路：
-
首先 使用 两个快慢指针 fast, slow, 并确保两者之间的间隔为N，
-
让fast 先行走 N 步， 然后 再让 fast, slow 同时移动， 这样 fast 到达结尾时， slow 到达了比他慢的N 步的节点位置， 这个位置便是我们要删除的 倒数第N个节点；
但是， 实践中， 当我们要删除某个节点时， 我们需要定位的位置是 待删除节点的前一个节点；
所有我们要定位的节点位置是， 待删除节点的前一个节点：
怎么办？
-
让fast 先行走 N + 1 步， 然后同时移动 fast, slow;
-
当 fast 到达结尾时， slow 比fast 慢了 N -1 步，
此时fast 到达了 末尾节点处， 那么slowNode 到达了删除节点的前一个节点了；
2.1 code
struct ListNode{
int val;
ListNode* next;
ListNode(int x): val(x), next(nullptr){}
};
class Solution{
public:
ListNode* removeNthFromEnd(ListNode* head, int n){
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* fastNode = new ListNode(0);
ListNode* slowNode = new ListNode(0);
fastNode = dummyHead;
slowNode = dummyHead;
int step = n + 1;
while( step --){ // 让快指针先走n+1 步； step = 0 时， 循环体不执行；
fastNode = fastNode->next;
}
while( fastNode != nullptr){ // 当fastNode 没有到达，最后一个节点时；
slowNode = slowNode->next;
fastNode = fastNode->next;
}
// 当fastNode 到达末尾指针时， slowNode 到达了 删除节点的前一个节点；
ListNode* tmpNode;
tmpNode = slowNode->next;
slowNode->next = slowNode->next->next;
delete tmpNode;
return dummyHead->next;
}
};
