Leetcode|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

24.

注意：涉及头节点的修改或者删除时，最好设置一个虚拟的头结点，方便简化代码，不必进行是否为头节点的的判断，简化code

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);//创建一个虚拟的头结点dummyHead->next = head;//建立联系ListNode* cur = dummyHead;//简化while(cur->next!=nullptr&&cur->next->next!=nullptr){//访问的合法性//记录临时地址的作用是方便找到结点，好进行新的连接ListNode* tmp = cur->next;//保存临时地址ListNode* tmp1 = cur->next->next->next;//保存临时地址cur->next = cur->next->next;//步骤一cur->next->next = tmp;//步骤二cur->next->next->next = tmp1;//步骤三cur = cur->next->next;//移动俩位，准备下一轮交换}ListNode* result = dummyHead->next;delete dummyHead;return result;}
};

 ListNode* cur = dummyHead;//这一步的操作也是始终知道头节点的位置，方便后续的链表输出

19.

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast!=nullptr){fast = fast->next;}fast = fast->next;while(fast!=nullptr){slow = slow->next;fast = fast->next;}ListNode* tmep = slow->next;slow->next = slow->next->next;delete tmep;//记得手动释放内存return dummyHead->next;}
};

面试题02.07(链表相交)

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lenA = 0, lenB = 0;while (curA != NULL) { // 求链表A的长度lenA++;curA = curA->next;}while (curB != NULL) { // 求链表B的长度lenB++;curB = curB->next;}curA = headA;curB = headB;// 让curA为最长链表的头，lenA为其长度if (lenB > lenA) {swap (lenA, lenB);swap (curA, curB);}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上（末尾位置对齐）while (gap--) {curA = curA->next;}// 遍历curA 和 curB，遇到相同则直接返回while (curA != NULL) {if (curA == curB) {return curA;}curA = curA->next;curB = curB->next;}return NULL;}
};

142

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr&&fast->next!=nullptr){slow = slow->next;fast = fast->next->next;//快慢指针相遇，此时从head和相遇点，同时查找直至相遇if(slow==fast){ListNode* index1 = fast;ListNode* index2 = head;while(index1!=index2){index1 = index1->next;index2 = index2->next;}return index1;//返回环的入口}}return nullptr;}
};

关于fast前进俩步的合法性判断：

为什么可以安全访问 fast->next->next？
链表的结构和指针移动的关系：在循环中，我们每次让 fast 走两步：fast = fast->next->next。
关键在于：只要我们能保证 fast 和 fast->next 都不为 nullptr，那么 fast->next->next 就一定是一个合法的访问。
fast != nullptr && fast->next != nullptr 的逻辑：如果 fast != nullptr 且 fast->next != nullptr 成立，意味着：
fast->next 是一个有效的节点（它的指针不为空）。
既然 fast->next 是一个有效节点，它的 next 域（即 fast->next->next）不一定为空，但一定是合法的访问。
如果 fast->next->next 是 nullptr，这只是意味着链表的终点到了，但访问它不会导致程序崩溃。
为什么不需要单独判断 fast->next->next？我们只需要判断两层的指针（fast 和 fast->next），因为算法的逻辑是：只有在 fast 能再往前移动时才继续循环。
如果 fast->next 是最后一个节点（即 fast->next->next == nullptr），那在本轮循环之后会退出，不会再执行下一次的 fast = fast->next->next。
总结
通过判断 fast != nullptr && fast->next != nullptr，我们确保了每次访问 fast->next->next 都是合法的。
即便 fast->next->next 是 nullptr，也只是说明链表结束了，并不会导致崩溃。下次循环时，会检测到不满足循环条件，程序会安全退出。
所以，这样的判断已经足够确保算法的安全性，不会出现对空指针的非法操作。