24. 两两交换链表中的节点

一时间没写出来，只需要管一个指针就够了，后面的两个指针每次循环定义下就ok了

class Solution {
public:
    // 只需要管一个指针就够了  后面的两个指针每次循环定义下就ok了
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* ptr = dummy;
        while (ptr != nullptr && ptr->next != nullptr && ptr->next->next != nullptr)
        {
            // 后面两个
            ListNode* one = new ListNode;
            one = ptr->next;
            ListNode* two = new ListNode;
            two = one->next;

            // 交换
            ptr->next = two;
            one->next = two->next;
            two->next = one;

            ptr = one;
        }
        return dummy->next;
    }
};

19. 删除链表的倒数第 N 个结点

没有难度，前后双指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* p1 = dummy, *p2 = dummy;
        for (int i = 0; i < n+1; i ++) p2 = p2->next;
        while (p2)
        {
            p2 = p2->next;
            p1 = p1->next;
        }
        p1->next = p1->next->next;
        return dummy->next;
    }
};

面试题 02.07. 链表相交

让两个指针都跑 a+b+c 的长度

需要注意的是两个都是nullptr就代表没有相交

class Solution {
public:
    // 让每个节点都跑 a + b + c
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode*p1 = headA;
        ListNode*p2 = headB;
        // 可能出现不相交的情况, 所以要让程序能够正常终止 => 能够都是nullptr后跳出来
        while (p1 != p2)
        {
            p1 = p1 == nullptr ? headB : p1->next;
            p2 = p2 == nullptr ? headA : p2->next;
        }
        return p1;
    }
};

142. 环形链表 II

双指针挺数学公式的

class Solution {
public:
    // slow是nb 入环点是a+nb  所以要让slow再跑a步
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr)
        {
            slow = slow->next;
            if (fast->next == nullptr) return nullptr;
            fast = fast->next->next;
            // 相遇了  slow已经走过nb了,fast走过2nb了 让slow再走a
            if (fast == slow)
            {
                fast = head;
                while (fast != slow)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};