本节内容

24. 两两交换链表中的节点
19.删除链表的倒数第N个节点
面试题 02.07. 链表相交
142.环形链表II
总结

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

建议：用虚拟头结点，这样会方便很多。

本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。

题目链接： https://leetcode.cn/problems/swap-nodes-in-pairs/
文章讲解： https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html

https://www.yuanql.top/2023/06/06/02_leetcode/24.%20%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9/

题目分析

首先设置一个虚拟的头节点，然后参照下图的方式交换相关的节点。

每次交换的时候，需要知道四个节点，分别为需要交换的两个节点，以及指向和指出的两个节点，通过此方式才能正常的进行一次循环。
结束的标志位为：一次循环中，需要进行交换的两个节点中有一个节点为null值，则直接退出循环，程序结束，返回计算结束后边的数值。

方案一

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode headNode = new ListNode();
        headNode.next = head;

        ListNode left = head, // 此处用于指向交换两节点的左节点
                right = null; // 此处用于指向交换两节点的右节点，
                            // 为什么赋值为null，而不是 left.next ： 不确定left是否为null，如果left为null，取left.next将会报空指针错误
        ListNode start = headNode,  // 此处为指向左节点的前一个节点
                end = null; // 此处为被右节点指向的后一个节点

        while (left != null && left.next != null) {
            right = left.next;
            end = right.next;

            start.next = right;
            right.next = left;
            left.next = end;

            start = left;
            left = end;
        }

        return headNode.next;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.2 MB,击败了41.91% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E6%80%9D%E8%B7%AF

其中的图片可以借鉴，显得更加的清晰，本质上和上述思路一致。

初始时，cur指向虚拟头结点，然后进行如下三步：

操作之后，链表如下：

看这个可能就更直观一些了：

代码实现

// 递归版本
class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;

        return next;
    }
}

class Solution {
  public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;      // 步骤三
            cur = firstnode; // cur移动，准备下一轮交换
        }
        return dumyhead.next;  
    }
}

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

建议：双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向第N个节点的前一个节点，建议先看视频。

题目链接： https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
文章讲解： https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

https://www.yuanql.top/2023/06/07/02_leetcode/19.%20%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%AC%20N%20%E4%B8%AA%E7%BB%93%E7%82%B9/

题目分析

双指针（滑动窗口），让一个节点先走，当其之间的差距达到 n 的时候，两个节点一起向前，等先走的节点走到为null值的时候，此时后一个节点所在的位置就是需要删除的位置

方案一

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode fast = dummy, // 走在前面的节点
                slow = dummy; // 走在后面的节点
        for (int i = 0; i < n; i++) { // 快的节点先走
            fast = fast.next;
        }
        while (fast.next != null) { // 两节点结伴前行
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next; // 移除从后数第 n 个节点
        return dummy.next;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.5 MB,击败了55.47% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

首先推荐使用虚拟头结点，这样方便处理删除实际头结点的逻辑，如果虚拟头结点不清楚，可以看这篇：链表：听说用虚拟头节点会方便很多？(opens new window)
定义fast指针和slow指针，初始值为虚拟头结点，如图：

fast首先走n + 1步，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：

本人的方案中此处行走步数是不一致的，因为我走的是 n 步，所以导致下一步循环判断的时候，我都是判断 fast.next 是否为null。
从执行上来看，走 n+1 步更优，少了一步调取 fast.next 而是直接对接 fast 的数值。

fast和slow同时移动，直到fast指向末尾，如题：

删除slow指向的下一个节点，如图：

代码实现

public ListNode removeNthFromEnd(ListNode head, int n){
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;

    ListNode fastIndex = dummyNode;
    ListNode slowIndex = dummyNode;

    //只要快慢指针相差 n 个结点即可
    for (int i = 0; i < n  ; i++){
        fastIndex = fastIndex.next;
    }

    while (fastIndex.next != null){
        fastIndex = fastIndex.next;
        slowIndex = slowIndex.next;
    }

    //此时 slowIndex 的位置就是待删除元素的前一个位置。
    //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
    slowIndex.next = slowIndex.next.next;
    return dummyNode.next;
}

面试题 02.07. 链表相交※

建议：注意数值相同，不代表指针相同。

题目链接： https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
文章讲解： https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

题目分析

因为曾经做过一次这个题目，以及记下来相关答案，所以对现在的我来说可能难度不大，但是当时刚开始接触到此题目的时候还是蛮搞人的，此题就是一瞬间的思路，就决定了以后的全部发展。

两个指针分别从 A 端和 B 端出发，走到null的时候在走对方的路，当其有交点的时候，两个走的路程一致，所以一定会在通过点上相遇，如果继续走，大家又同时走到null了，此时就是没有节点。

null == null 的返回值为 true，所以循环只需要设置条件 不相等进行执行即可

方案一

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA = headA, tempB = headB;
        while (tempA != tempB) {
            if (tempA != null) { // 为什么使用 tempA != null ，而不使用 tempA.next != null？
                // 使用 tempA != null 相较于 tempA.next != null 在循环上多走了两步，但是其可以将 null 带入到循环中去判断
                // 而 tempA.next != null 将不会将 null 节点带入到循环中去判断，将会导致没有相交接入点的时候，一致死循环下去，其
                //      在程序中也解决，无非是加响应的标志位，这样会导致代码的逻辑更加复杂，相关的系统资源开销也会更高。
                tempA = tempA.next;
            } else {
                tempA = headB;
            }
            if (tempB != null) {
                tempB = tempB.next;
            } else {
                tempB = headA;
            }
        }
        return tempA;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了98.04% 的Java用户
内存消耗:45.1 MB,击败了60.51% 的Java用户

分析

时间复杂度：
O( n + m )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

此中所介绍的方法感觉不如方案一相对简单

交点不是数值相等，而是指针相等。

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

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

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
否则循环退出返回空指针。

代码实现

public 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) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

142.环形链表II※

建议：算是链表比较有难度的题目，需要多花点时间理解确定环和找环入口。

题目链接： https://leetcode.cn/problems/linked-list-cycle-ii/
文章讲解： https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

https://www.yuanql.top/2023/06/08/02_leetcode/142.%20%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8%20II/

题目分析

方法一：将数据放入到 hashMap 中，判断新加入的数据是否在hashmap中，如果出现，则代表刚刚出现的节点就是入环的节点坐标。

但是其空间复杂度较高，达不到进阶的要求。

方法二：双指针 –> 此方法比较绝妙，也是因为本人曾经做过一次本题才能理解（了解）此方法

如上图所示，首先设置两个快慢指针，快指针每次走两格，慢指针每次走一格。如果有环的话，快慢指针一定会在环内相遇，此时记慢指针走了 a+b 段路程，快指针走过了 a+b+n*(b+c) 端路程，因为其速度是两倍的关系，所有可得图中所示的相关公式。
根据公式推导可知，a端的路程和剩余的c端路程的距离相等，此时需要两个指针分别从后节点以及相遇的节点出发，最终想遇到的节点就是入环的节点。

更加详细的内容可点击以下相关链接：

本人的个人博客： https://www.yuanql.top/2023/06/08/02_leetcode/142.%20%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8%20II/
官方题解： https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
代码随想录： https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#_142-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8ii

方案一：哈希表

将数据放入到 hashMap 中，判断新加入的数据是否在hashmap中，如果出现，则代表刚刚出现的节点就是入环的节点坐标。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> listNodes = new HashSet<ListNode>();
        while (!listNodes.contains(head) && head != null) {
            listNodes.add(head);
            head = head.next;
        }

        return head;
    }
}

结果

解答成功:
执行耗时:3 ms,击败了16.87% 的Java用户
内存消耗:42.3 MB,击败了65.65% 的Java用户

分析

时间复杂度：
O( n )
hashset的add() 、contains() 方法的时间复杂度均为 O(1)

空间复杂度：
O( n )

方案二：快慢指针

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) { // 此处用于特殊判断当前节点为null，或者下一个节点为null，防止下方赋值报错
            return null;
        }

        ListNode fast = head.next.next, slow = head.next;

        while (fast != null && fast.next != null && fast != slow) {
            fast = fast.next.next;
            slow = slow.next;
        }

        if (fast != slow) { // 此处用用于判断是否有环，不相等的时候一定是没有环的
            return null;
        }

        fast = head;
        while (fast != slow) { // 牵起手，一起走
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:42.8 MB,击败了14.96% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#_142-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8ii

思路

主要考察两知识点：

判断链表是否环
如果有环，如何找到这个环的入口

判断链表是否有环

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
那么来看一下，为什么fast指针和slow指针一定会相遇呢？
可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。
会发现最终都是这种情况，如下图：

fast和slow各自再走一步， fast和slow就相遇了
这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
动画如下：

如果有环，如何找到这个环的入口

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示头结点到环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？
先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

动画如下：

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候效果是一样的，一样可以通过这个方法找到环形的入口节点，只不过，index1 指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

疑问：为什么第一次在环中相遇，slow的步数是 x+y 而不是 x + 若干环的长度 + y 呢？

具体回答请看代码随想录： https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E8%A1%A5%E5%85%85

代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

总结※

代码随想录关于链表的总结篇： https://programmercarl.com/%E9%93%BE%E8%A1%A8%E6%80%BB%E7%BB%93%E7%AF%87.html

虚拟头的使用

在做题的时候一定要想起来使用虚拟头，主要涉及到对头节点的增删等内容，一定要想起使用虚拟头，可以减少很多的非必要的逻辑判断，使代码写起来更加丝滑。

双指针

双指针不仅可以在数组中使用，也可以在链表中进行使用，使用双指针记录一些中间状态，可以有些解决循环的使用

哈希表

虽然在做的几道题中哈希表都不在最佳的方案，但是其相对容易好像，至少可以把题目做出来

04、第二章 链表part02

本节内容

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

题目分析

方案一

结果

分析

代码随想录

代码实现

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

题目分析

方案一

结果

分析

代码随想录

代码实现

面试题 02.07. 链表相交※

题目分析

方案一

结果

分析

代码随想录

代码实现

142.环形链表II※

题目分析

方案一：哈希表

结果

分析

方案二： 快慢指针

结果

分析

代码随想录

思路

判断链表是否有环

如果有环，如何找到这个环的入口

代码实现

总结※

虚拟头的使用

双指针

哈希表

相关数学知识的应用

04、第二章链表part02

方案二：快慢指针