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，也只是说明链表结束了，并不会导致崩溃。下次循环时，会检测到不满足循环条件，程序会安全退出。
所以，这样的判断已经足够确保算法的安全性，不会出现对空指针的非法操作。