代码随想录算法训练营Day04 | LeetCode 24 两两交换链表中的节点、LeetCode19 删除链表的倒数第N个节点、LeetCode面试题02.07 链表相交、LeetCode14...

今日学习的视频和文章

代码随想录链表基础
代码随想录两两交换链表的节点
代码随想录删除链表的倒数第N个节点
代码随想录链表相交
代码随想录环形链表II
王道数据结构复习指导链表部分王道计算机考研数据结构_哔哩哔哩_bilibili

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

24. 两两交换链表中的节点 - 力扣（Leetcode）

经过对链表知识的复习以及对“虚拟节点”思想的理解，这道题目初见时我写起来感觉比较简单，只需要添加一个虚拟头节点，然后模拟各个节点的next的调整过程即可。
我初见的题解和代码随想录的题解比起来还是有差距的，其实不需要left、pre等这么多保留临时节点的变量，是否需要保留临时节点，应该根据各个节点的next的调整过程来判断，如果调整过程中还能取到这个节点，则可以不需要保留临时节点。可见，每次循环中cur的选取，以及各个节点的next的调整顺序，对于代码实现的影响是很大的。

image.png

初见题目的完整题解代码如下

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;
    ListNode* left = dummyHead;
    ListNode* pre = dummyHead->next;
    ListNode* cur = head ? head->next : nullptr;
    ListNode* next = nullptr;
    while (cur) {
        left->next = cur;
        next = cur->next;
        cur->next = pre;
        pre->next = next;

        left = pre;
        pre = next;
        cur = next ? next->next : nullptr;
    }
    head = dummyHead->next;
    delete dummyHead;
    return head;
}

而代码随想录的cur选取是两两交换的一组节点的前一个节点，显然需要两两交换的节点都可以用cur取到，只需要暂存cur->next即可。

image.png

代码随想录给出的题解代码：

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
    dummyHead->next = head; // 将虚拟头结点指向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; // cur移动两位，准备下一轮交换
    }
    return dummyHead->next;
}

看了讲解之后改良的题解代码，其实还可以再少保存一个临时节点，只需要暂存cur->next即可：

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;
    ListNode* cur = dummyHead;
    while (cur->next != nullptr && cur->next->next != nullptr) {
        ListNode* temp = cur->next;
        // 让节点cur的next指向节点2
        cur->next = cur->next->next;
        
        // 此时节点2的next还指向节点3，所以可以用来让节点1的next来指向节点3
        temp->next = cur->next->next;
        
        // 让节点2的next指向节点1
        cur->next->next = temp;
        
        // cur指向节点1，尝试进入下一次交换
        cur = temp;
    }
    head = dummyHead->next;
    delete dummyHead;
    return head;
}

上述题解对应的模拟步骤和代码随想录的步骤有所不同，示意如下：

image.png

LeetCode19 删除链表的倒数第N个节点

19. 删除链表的倒数第 N 个结点 - 力扣（Leetcode）

初见题目时的想法：链表长度未知，先遍历一遍得到链表长度，再算出要删除的节点的位置。

题解代码如下：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    int size = 0;
    ListNode* cur = head;
    while (cur) {
        cur = cur->next;
        size++;
    }

    int target = size - n;
    cur = dummyHead;
    while (target--) {
        cur = cur->next;
    }
    cur->next = cur->next->next;

    head = dummyHead->next;
    delete dummyHead;
    return head;
}

看到题目提示能不能只用一遍扫描来完成，思路如下：
- 首先，倒数第n个节点和最后一个节点的位置距离固定为n，那么，可以用一个长度为n的窗口去扫描链表，当这个窗口的尾部到达了链表结束位置时，删除窗口的第一个元素。
- 于是产生了双指针的想法，用一个fast指针和一个slow指针来表示这个滑动的窗口。
- fast和slow相距n个节点，由于题目限定了n都是合理的值，就不用考虑n值是否越界了
- fast和slow一起扫描链表，直到fast->next指向NULL，用slow来删除目标节点。
  - 为什么是fast->next？因为要删除一个节点，应该让slow指向倒数第n个节点的前一个节点，所以在下面的代码里让fast->next指向NULL时退出循环，就正好让slow指向我们要的位置。

完整题解代码如下：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    ListNode* slow = dummyHead;
    ListNode* fast = dummyHead;
    while (n--) {
        fast = fast->next;
    }
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* del = slow->next; 
    slow->next = slow->next->next;
    delete del;

    head = dummyHead->next;
    delete dummyHead;
    return head;
}

听了一遍讲解，发现自己这道题能考虑得比较清楚了，但还是要多复习多练习多总结。

LeetCode面试题02.07 链表相交

面试题 02.07. 链表相交 - 力扣（Leetcode）

初见题目时的想法：
- 起初最令我疑惑的地方是如何判断从哪里开始链表相交，但似乎题目规定了只要A链表的一个节点的值和B链表的一个节点的值相等，则A链表该节点之后的值与B链表节点之后的值都相等，所以只需要找两个链表从各自哪个节点的值开始相等，即可找到相交的位置。
- 然而到这里我就理解错题意了，链表相交是两个链表各自的某个节点的next指向的节点相同，并非值相等。
- 那么，最简单的方法就是让A链表的每个节点都与B链表的节点逐个比较，这样的时间复杂度显然是 $O(n^2)$
- 观察题目所给的例子，相交的链表是从倒数的第n项开始相交的，而A链表和B链表相交之前的项的最后一个节点是对齐的。
- 如果A链表和B链表长度不等的话，可以从哪里开始相交呢？
  - 设A链表长度为 $L_A$ ，B链表长度为 $L_B$ ，假设 $L_A>L_B$ 。
  - A链表是不是能包含B链表？就是说是否*headB指向的其实是A链表的某个非头节点。但这里应该是我想复杂了，题目说是两个链表，如果是这种情况，应该是不符合题意的。所以，A链表比B链表长的部分，应该是不能与B链表相交的，那么节点的地址值的比较应该从A链表的第 $L_A-L_B$ （从0开始）个节点开始。

完整的题解代码如下：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* curA = headA;
    ListNode* curB = headB;

    int lthA = 0;
    while (curA) {
        curA = curA->next;
        lthA++;
    }
    int lthB = 0;
    while (curB) {
        curB = curB->next;
        lthB++;
    }

    curA = headA;
    curB = headB;
    if (lthA < lthB) {
        swap(lthA, lthB);
        swap(curA, curB);
    }
    int align = lthA - lthB;
    while (align--) {
        curA = curA->next;
    }

    while (curA != nullptr && curB != nullptr) {
        if (curA == curB) return curA;
        curA = curA->next;
        curB = curB->next;
    }

    return nullptr;
}

LeetCode142 环形链表

142. 环形链表 II - 力扣（Leetcode）

初见题目时的想法：
- 如何判断链表是否出现了环？我第一反应是使用哈希表，由于每个节点的地址都是唯一的，所以可以以地址作为哈希表的key值来存储已经遍历过的节点。我看到题目有进阶提示为使用O(1)的空间，但使用哈希表的话显然使用的空间为O(n)。

使用哈希表的题解代码：

ListNode *detectCycle(ListNode *head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    ListNode* cur = dummyHead;
    unordered_map<ListNode*, int> nodeMap;
    int index = 0;
    while (cur) {
        if (nodeMap.find(cur) != nodeMap.end()) {
            delete dummyHead;
            return cur;
        }
        else {
            nodeMap.insert({cur, index});
        }
        cur = cur->next;
    }

    return nullptr;
}

如何使用O(1)的空间来解决这道题呢，我思考了很久。然后想到了有环的话，遍历出的节点地址就会有周期性。
- 在有环的情况下，以不同的方法去获取节点地址，就有可能获取相同的节点地址，不同的方法能获取到相同的地址，说明有环，那么用什么样的方法呢？
- 不同至少要有两个方法去遍历，因为今天的题目用过，我又想到了双指针。以下是我初见题目时的思考
  - 不同的遍历方式，用快慢指针来理解的话，就是slow每次移动一位，fast每次移动两位，如果在循环中出现slow == fast情况，则说明有环。
  - 但我不知道如何求环的入口的位置，看了讲解之后，这个求解方式确实超出我目前能力范围，还是先理解了这道题再继续努力吧。
我对这道题的数学证明过程的理解

image.png

slow表示slow经过的节点数，fast表示fast经过的节点数，x为从dummyHead到环的入口的节点数（不包括dummyHead），y为从环的入口到相遇的位置的节点数，z表示从相遇的位置到环的入口的节点数。
由于fast每次经过2个节点，slow每次经过1个节点，所以可以得到：
$2(x+y)=x+y+n(y+z)(n \ge 1)$
上式变形得

$x=(n-1)(y+z)+z(n \ge 1)$

到这一步，我是这样理解的：
- 假设有一个index1从dummyHead开始每次移动一个节点，index1移动到环的入口经过的节点数显然为x，即上述等式的左边。
- 有一个index2从slow和fast的相遇位置开始每次移动一个节点，移动到环的入口处经过的节点数为(n-1)(y+z)+z，即上述等式的右边。
- 上述等式就是说，index1与index2相遇时，index2可能在环内转了n-1圈。但我们现在不关心index2转了几圈，无论index2转了几圈，index1与index2第一次相遇时的位置一定是环的入口的位置！

完整题解代码如下：

ListNode *detectCycle(ListNode *head) {
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;

    ListNode* slow = dummyHead;
    ListNode* fast = dummyHead;
    while (slow != nullptr && fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = dummyHead;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}