Junyuan's Homepage

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

题目链接：click here
文章讲解：click here
题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路：
这道题要求两两交换，所以如果如果节点数少于两个就直接退出
交换的时候，要遵循昨天总结的“先记录，再修改”的原则，特别是为了能继续遍历链表，需要先记录好next，才能修改next。

循环内部的具体的操作比较简单：拿到三个连续节点，last，cur 和 kid，
交换：cur 和 kid 要交换，于此行为相配合的是这两个节点的前、后两个节点，即
重指：last 的 next 要指向 kid，cur 的 next 则要指向 kid 的下一个节点 kkid。
位移：随后 last 指针向右移动两位，到原 kid 现 cur 处，cur 指针顺延到 last 指针后一位处。
循环上述交换、重指、位移操作即可。

循环从哪里开始？
用虚拟头节点 vhead ，减少不必要的特殊处理。
所以可以从 last = vhead 开始，这样就算一共只有两个节点，按上面的流程也是能满足要求的交换他们的位置。

什么时候退出？
单次交换完成后，last 依旧是有效的，所以需要看的是 cur 及其后一位，也就是下一次进行交换的两个节点是否都有效，只要有一个无效，就可以退出循环了。

代码：

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (!head || !(head->next))
            return head;

        ListNode *vhead = new ListNode(0, head);
        ListNode *last = vhead;
        ListNode *cur = last->next;

        while (cur && (cur->next))
        {
            auto kid = cur->next;
            auto kkid = kid->next;
            kid->next = cur;
            cur->next = kkid;
            last->next = kid;

            last = cur;
            cur = last->next;
        }

        return vhead->next;
    }
};

时空复杂度分析：
完整遍历链表一次：O(n) 时间复杂度
没有额外存储：O(1) 空间复杂度

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

题目链接：click here
文章讲解：click here
题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
思路：
基础要求：
先遍历整个链表，一共有多少个，然后看倒数第 n 个是正数第几个，再遍历到该位置进行删除即可。
进阶要求：
很奇怪啊很奇怪，我怎么能正好遍历到倒数第 n 个节点上？我似乎只能确保自己遍历到最后一个节点上了。
这俩节点有什么关系呢？那就是俩节点之间的距离是确定的，定义为从一个节点到另一个节点要走多少步。
显然，倒数第 n 个节点与倒数第 1 个节点之间的距离为 n-1。
那么，当我遍历的时候，采用双指针法：
让快指针先行 n-1 步，使得双指针的节点距离是 n-1，
那么当快指针到最后一个节点的时候，慢指针正好走到要删除的那个节点上。

实现中要注意，为了删一个节点，最好是拿到它的前一个节点，进行跳链接到它后一个节点来实现删除。
所以快指针要先偷跑一步，好让慢指针届时指向要删除的节点的前一个节点。
为了减少对头节点的特殊处理，采用虚拟头节点。

代码：

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *vhead = new ListNode(0, head);
        auto slow = vhead;
        auto fast = vhead->next; // 偷跑一步

        for (int i = 0; i < n - 1; i++)
        {
            fast = fast->next; // 再跑n-1步
        }

        while (fast->next) // 当快指针到达最后一个节点时，慢指针到了该删的节点的前一个。
        {
            fast = fast->next;
            slow = slow->next;
        }

        auto temp = slow->next;
        slow->next = slow->next->next; // 跳链接
        delete temp;                   // 删除
        temp = nullptr;

        return vhead->next;
    }
};

面试题 02.07. 链表相交

题目链接：click here
文章讲解：click here
题目描述：简述为，两个单链表，找他们俩之间相交的部分的起点。

思路：

我的想法：
既然节点内有数据，且数据具有正数的特点，那么我先遍历A链表，把里面的数据全部改为负数。
再遍历B链表，挨个检查里面的数据是不是负数，是则意味着这个节点在A中也存在，即为二者的交点。
按照题目描述：不允许修改链表的结构，我并没有修改结构，只是修改了数据罢了。
不过提交测试后发现链表的数据也不能修改，那么就在返回交点结果前，再遍历一次A，把内部的值都改为原值即可。

代码：

class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *vheadA = new ListNode(0, headA);
        while (headA)
        {
            headA->val *= -1;
            headA = headA->next;
        }

        while (headB)
        {
            if (headB->val < 0)
            {
                headA = vheadA->next;
                while (headA)
                {
                    headA->val *= -1;
                    headA = headA->next;
                }
                return headB;
            }
            else
            {
                headB = headB->next;
            }
        }
        headA = vheadA->next;
        while (headA)
        {
            headA->val *= -1;
            headA = headA->next;
        }
        return nullptr;
    }
};

时间复杂度：O(2n+m)=O(n+m)
空间复杂度：O(1)
讲解中的思路：
利用了一个链表相交的特点，那就是两个非循环链表如果相交，那么必然拥有相同的终点。
利用这一特点，就比较好检查两个链表有没有相交了，以及相交在何处了。
如果两个链表一样长，那尾部本就是对齐的，直接以相等速度向后遍历，挨个比较当前节点的地址是否一样，是则相交。
如果两个链表不一样长，根据上述特性，若他们相交，必然拥有相同的终点，
于是乎先把尾部对齐，即让较长链表的迭代指针先走几步。
然后再两个迭代指针一起向前走，并挨个比较当前节点的地址是否一样，是则相交。
时间复杂度：O(2n+2m)=O(n+m)
空间复杂度：O(1)

我实现的代码：

class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *vheadA = new ListNode(0, headA);
        ListNode *vheadB = new ListNode(0, headB);

        auto temp_a = vheadA->next;
        int size_a = 0;
        while (temp_a)
        {
            size_a++;
            temp_a = temp_a->next;
        }

        auto temp_b = vheadB->next;
        int size_b = 0;
        while (temp_b)
        {
            size_b++;
            temp_b = temp_b->next;
        }

        temp_a = vheadA->next;
        temp_b = vheadB->next;
        int iter_size = 0;
        if (size_a > size_b)
        {
            int offset = size_a - size_b;
            iter_size = size_b;
            while (offset--)
            {
                temp_a = temp_a->next;
            }
        }
        else if (size_a < size_b)
        {
            int offset = size_b - size_a;
            iter_size = size_a;
            while (offset--)
            {
                temp_b = temp_b->next;
            }
        }
        else
        {
            iter_size = size_a;
        }

        while (iter_size--)
        {
            if (temp_a == temp_b)
            {
                return temp_a;
            }
            else
            {
                temp_a = temp_a->next;
                temp_b = temp_b->next;
            }
        }

        return nullptr;
    }
};

142. 环形链表II

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

不允许修改链表。
思路：
这个技巧性太强了，属于是必背题，之前刷过，所以依稀记得要快慢指针，快指针每次跳两格，慢指针每次跳一格。
但是后续记得不太清楚了，于是又自己推理了一通：

假设链表入环前的长度为 s ，环的长度为 c
当慢指针走到入口处时，共 s 步，快指针已经走了 2s 步，在环前、环上分别走了 s 步
很明显，快指针此时距离入口处的慢指针有 c - s 步距离（先假设环长 c 大于环前距离 s）。
现在把二者在环内的运动视为追赶运动，也就是快指针每次比慢指针快一步，他俩之间的距离就缩小一步。
c - s 步的距离需要 c - s 次运动。
追赶上时，慢指针从入口处前向运动了 c - s 步，二者都停留在这个位置。

下面的内容就是之前记不太清楚的后续：

精髓的地方到了：此时二者再走 s 步就能回到环入口，s 正好也是从链表头到环入口的距离。
于是，把慢指针移动到链表头，快指针位置不变，二者都以单步1格的速度向前走
当二者再次相遇时，就正好都处在环的入口处了。

如果是环长 c 等于环前距离 s 的时候，更简单了，二者第一次相遇就在入口处，所以上述方法也能处理。

如果是环长 c 小于环前距离 s 的时候，
当慢指针走到入口处时，共 s 步，快指针已经走了 2s 步，在环前、环上分别走了 s 步
那么快指针此时距离入口处有多远呢？
首先看快指针超出入口处多远：s - c？应该是 s - n * c，这个 n 最小为 1。记为 y = s - n * c < c

所以可知快指针此时距离入口处的慢指针为 c - y 步，不论这个值具体是多少，但它都小于 c。
那么根据追赶运动每次会缩进快慢指针之间的距离一格，共需要 c - y 步，二者相遇。

慢指针从入口处累计走了 c - y 步，所以二者相遇的位置也就是环上的 c - y 处

此时把慢指针移动到链表头，让他再以单格的速度跳到环入口，需要 s 步
快指针也以单格的速度，从刚刚双指针相遇的地方向前跳 s 步，将到达 c - y + s 处。
c - y + s = c - (s - n * c) + s = (n * c + c)
显然，由于 s > c，所以需要用上面这个结果对 c 取模运算，才能得到最终快指针的位置：
(n * c + c) % c = 0，所以此时快指针也正好回到环入口了。

综上，各种情况都能用上述算法处理。

代码：

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        if (!head)
        {
            return nullptr;
        }

        auto fast = head;
        auto slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast)
            {
                slow = head;
                while (fast != slow)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
两两交换链表中的节点：模拟题，需要把握循环块内的操作：交换、重指、移动，以及循环退出条件：下一次操作的两个节点任一无效。
删除链表的倒数第N个节点：根据确定性的能遍历到链表尾 + 待删除节点与链表尾的距离信息，用双指针控制相同的距离，来实现快指针到尾部时，慢指针指向待删除节点的前一个节点（快指针需要偷跑1格）。
链表相交：利用相交链表尾部对齐的特性，先将长短链表变成尾部对齐，忽略长链表的前部分，再逐一比对地址即可确认是否相交。
环形链表II：技巧题，直接记解法：快慢双指针，快的跳2格，慢的跳1格，相遇后慢指针移动到链表头，二者一起以1格速度移动，再次相遇处即为环形入口。
耗时：3h

Junyuan Lu(陆俊元)

代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II

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

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

面试题 02.07. 链表相交

142. 环形链表II

今日收获