随想录Day4|24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表Ⅱ

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

文章讲解

视频讲解

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

第一想法

链表长度的奇偶应该会影响，应该也需要虚拟头节点，逻辑应该是pre指向这个节点对前面的节点，cur1指向节点对的第一个，cur2指向节点对的第二个，然后重新穿链表（修改三根线），这里大家跟着那三行代码画画图就知道了。pre的下一个指向cur2，cur1的下一个指向原本cur2的下一个，然后cur2的下一个指向cur1。

需要注意的是更新pre和cur1的时候可以不判空。新的pre是原来的cur1，它就是刚刚处理过的节点对中（现在是）第二个元素，而如果原本这个节点对后面没有东西了，那么新的cur1就会是nullptr，如果直接写新的cur2 = cur1->next就会出现对空指针取next。

用时18min~

ListNode *swapPairs(ListNode *head)
{
    ListNode *dummyhead = new ListNode(0, head);
    ListNode *pre = dummyhead;
    ListNode *cur1 = head;
    if (!head)
        return head;
    ListNode *cur2 = head->next;

    while (cur2)
    {
        pre->next = cur2;
        cur1->next = cur2->next;
        cur2->next = cur1;
        // 注意后移指针时需要判空
        pre = cur1;
        cur1 = pre->next;
        if (!cur1)
            return dummyhead->next;
        cur2 = cur1->next;
    }
    return dummyhead->next;
}

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

文章讲解

视频讲解

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

第一想法和纠正

还是虚拟头节点，最后返回dummyhead->next。最朴素的做法就是数长度，第二次遍历定位到倒数第n个，然后删除。但是我已经看见了！进阶！“你能尝试使用一趟扫描实现吗？”那必须尝试。

删除节点的时候需要用到它的前一个节点（用于重穿链表），~~所以扫描的时候一定要保留pre和cur，其中cur是要删除的节点。~~并不需要把cur一路上同步往后移！只要那个pre即可（也就是后文的slow），只需要在删的时候用一个cur保存那个待删除节点。

看了随想录题解的想法

我是懒狗，不想动脑了，然后看了这句话豁然开朗。

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

fast比slow快n步，然后fast停在链表的最后一个节点，slow停在待删除节点cur的前一个。梳理一下n = 1的特殊情况：是可以正常取得cur->next的，因为cur不会是nullptr。

用时18min~

ListNode *removeNthFromEnd(ListNode *head, int n)
{
    ListNode *dummyhead = new ListNode(0, head);
    ListNode *fast = dummyhead;
    ListNode *slow = dummyhead;
    while (n--)
        fast = fast->next;
    while (fast->next)
    {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode *cur = slow->next;
    slow->next = cur->next;
    delete cur;
    return dummyhead->next;
}

面试题 02.07. 链表相交

文章讲解

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

第一想法

X形交叉的链表，那个交汇点算不算？按照题目的意思，应该是自这个点起，后面共用一切，val和next全都保持一致。

哦哦，根本不会有这种情况，除非那个交汇点有两个next指针，显然不可能。那没事了！

那就A移动一次，AB比较，B移动一次，AB比较，如此往复……

可是如果错过了怎么办？如果交汇点之前A特别短B特别长，按照两边同等速度走，当B走到交汇点，A已经走过了。

也不可能A在每个点等B扫完一整遍，那样时间复杂度会爆炸为\(O(mn)\)的。

看了随想录题解的想法

速通懒狗再次发动偷看技能！（才没有，其实卡尔也建议我们先看看，我每次很守信的我都只看三四行）

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB末尾对齐的位置。

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

啊！这样就好了，因为如果有交汇，尾段都是对齐的，所以距离链表尾的长度肯定是一样的。curA和curB总是保存距离自己的链表尾一样，同时向后移动。

用时20min~

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    ListNode *curA = headA;
    ListNode *curB = headB;
    int m = 0, n = 0;
    // 统计长度
    while (curA)
    {
        m++;
        curA = curA->next;
    }
    while (curB)
    {
        n++;
        curB = curB->next;
    }
    // 记得重置cur
    curA = headA;
    curB = headB;
	// 长的那个先往后走
    if (m > n)
    {
        int diff = m - n;
        while (diff--)
            curA = curA->next;
    }
    else
    {
        int diff = n - m;
        while (diff--)
            curB = curB->next;
    }
    // 开始比较
    while (curA != curB && curA)
    {
        curA = curA->next;
        curB = curB->next;
    }
    return curA;
}

142. 环形链表Ⅱ

文章讲解

视频讲解

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

第一想法

很久以前我看过视频的，记得是快慢指针法，在某处相遇，就是环的入口，我当时还感叹特别巧妙。看看能不能凭自己的记忆和推理想出来。

入环点会有两个箭头指过来，直线部分的前驱节点和环中指回来的节点。所以有两种方式到达它，一个是从头往后走（第一次经过），一个是从环里回到它（之后的多次经过）。

啊！如果环的长度为m，让fast先走m步，slow从头开始走，那么它们一起向后移的时候，一定会同时到达入环点。想象一个400m的环形跑道，前面有50m的直道，fast先跑400m（也就是直道的50m和环道的350m），距离第一圈跑完还有50m，此时slow从直道开始跑，则二人正好在入环点汇合。

那么该如何得到这个m呢？肯定是一上来不知道环具体在哪开始，但是有某种方法获得环的长度。甚至在此之前还要判断有没有环，没有环一定会走到nullptr，可是要走多远才可以确定呢，104吗？这个边界范围给我们是让我们这么用的吗……

看完随想录题解的想法

进行一个认怂，再度迎来恍然大悟。（只看这一句，剩下的自己推！）

判断链表是否有环：可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。

为什么可以保证相遇？和步长有关，较小的步长为1、步长差为1，已经是最小粒度了。

假设直线部分长为d，slow走了n步，fast走了2*n步相遇，而fast和slow相遇说明fast快它一圈（m步），则它们的路程差n实际上就是环长m。妙啊妙啊妙啊。

而且这样其实不需要显式地获得m，在相遇之后让ahead从fast的位置开始，behind从head的位置开始，步长均为1，下次相遇正是入环点！

用时52min~

ListNode *detectCycle(ListNode *head)
{
    if (!head)
        return nullptr;
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            ListNode *ahead = fast;
            ListNode *behind = head;
            while (ahead != behind)
            {
                ahead = ahead->next;
                behind = behind->next;
            }
            return ahead;
        }
    }
    return nullptr;
}