leetcode——链表

扫测资讯 2024-12-09 18:07 30 0

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：

链表中节点的数目范围是 [0, 5000]

-5000 <= Node.val <= 5000

进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

原理

该算法使用迭代的方式反转链表。我们通过三个指针来进行操作：

pre : 用来保存已经反转部分的链表的尾部（即当前节点的前一个节点）。

cur : 用来表示当前正在处理的节点。

temp : 用来暂存 cur.next 节点，以便在改变 cur.next 后，仍能继续访问下一个节点。

具体步骤：

初始化 ：

pre = null : 反转后的链表头节点的前一个节点是 null （反转后的链表尾部的指针）。

cur = head : cur 用于遍历原链表的节点。

temp = cur.next : temp 用于存储 cur.next ，因为一旦我们改变了 cur.next ，我们就不能再访问原链表的下一个节点。

遍历链表 ：

cur != null : 循环继续，直到 cur 为 null ，即处理完所有节点。

temp = cur.next : 暂存当前节点的下一个节点。

cur.next = pre : 反转当前节点的指针，让 cur.next 指向 pre ，将当前节点链接到已经反转的部分。

pre = cur : 更新 pre 指针， pre 向后移动一位，指向当前节点。

cur = temp : 更新 cur 指针， cur 向后移动一位，指向下一个节点。

返回反转后的链表 ：

最终 pre 指向的是新的头节点（反转后的链表的第一个节点），所以返回 pre 。

时间复杂度：

时间复杂度是 O(n) ，其中 n 是链表的节点数。我们遍历链表一次，每个节点的操作时间是常数时间。

空间复杂度：

空间复杂度是 O(1) ，只用了常数空间，除了存储链表节点的指针变量，没有使用额外的空间。

代码

class Solution {
    // 定义反转链表的方法
    public ListNode reverseList(ListNode head) {
        // 如果链表为空或者只有一个节点，直接返回 head
        if (head == null || head.next == null) {
            return head;
        }

        // pre 指针表示反转后的链表的前一个节点，初始化为 null
        ListNode pre = null;
        // cur 指针表示当前处理的节点，初始化为头节点
        ListNode cur = head;
        // temp 用来暂存 cur.next 节点
        ListNode temp = cur.next;

        // 遍历链表，直到 cur 为 null（即所有节点都被反转）
        while (cur != null) {
            // 将 cur.next 暂存到 temp
            temp = cur.next;
            // 将 cur.next 指向 pre，完成反转
            cur.next = pre;
            // pre 和 cur 都向后移动一位
            pre = cur;
            cur = temp;
        }

        // 返回反转后的链表的头节点，实际上是 pre 指针
        return pre;
    }
}

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

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

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：

链表中结点的数目为 sz

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

进阶： 你能尝试使用一趟扫描实现吗？

原理

这段代码的目标是 删除链表中的倒数第 n 个节点 。为了高效实现这一目标，采用了 双指针 技巧，即通过使用 slow 和 fast 两个指针来一次遍历完成操作。

步骤分析：

创建虚拟头结点 ：

创建一个虚拟的头结点 dummyNode ，它指向 head ，目的是简化边界条件的处理，特别是当需要删除链表的头结点时。

例如，在链表只有一个节点或删除的是第一个节点时，直接操作 dummyNode.next 就能轻松处理这些情况。

初始化 slow 和 fast 指针 ：

slow 和 fast 都初始化指向虚拟头结点 dummyNode 。

slow 用来最终指向要删除节点的前一个节点。

fast 用来辅助定位倒数第 n 个节点。

移动 fast 指针 n 步 ：

通过 for 循环，让 fast 指针先向前移动 n 步。此时， fast 和 slow 之间的距离为 n 。

如果链表的长度是 sz ，则 fast 会指向倒数第 n 个节点的前一个节点。

同步移动 slow 和 fast 指针 ：

让 slow 和 fast 同时向前移动，直到 fast 到达链表的末尾（即 fast.next == null ）。此时， slow 指针正好指向倒数第 n 个节点的前一个节点。

例如，当 fast 到达链表的最后一个节点时， slow 指向的是要删除的节点的前一个节点。

删除倒数第 n 个节点 ：

删除节点的操作是通过 slow.next = slow.next.next 来完成的，即让 slow 的 next 指向 slow.next 的下一个节点，从而跳过了倒数第 n 个节点。

返回新链表的头结点 ：

最后，返回 dummyNode.next ，因为虚拟头结点的下一个节点即为删除后的链表的头结点。

举例说明：

考虑链表 [1, 2, 3, 4, 5] ，并且要删除倒数第 2 个节点（即值为 4 的节点）：

初始状态：

slow 和 fast 都指向 dummyNode ，即虚拟头结点。

移动 fast 指针 2 步：

fast 指向节点 2。

同步移动 slow 和 fast 指针，直到 fast 到达链表的末尾：

fast 最终指向节点 5， slow 则指向节点 3。

删除倒数第 2 个节点：

slow.next = slow.next.next ，即 slow.next 从指向节点 4 改为指向节点 5，完成删除。

最终，链表变为 [1, 2, 3, 5] 。

时间复杂度：

时间复杂度是 O(n) ，其中 n 是链表的节点数。我们只遍历链表一次。

空间复杂度：

空间复杂度是 O(1) ，除了使用常数空间的指针变量外，没有额外的空间开销。

代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头结点（dummyNode），它指向头结点，便于处理删除头节点的情况
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        // slow 和 fast 都初始化为虚拟头结点
        ListNode slow = dummyNode;
        ListNode fast = dummyNode;

        // 将 fast 指针向前移动 n 个节点，确保 slow 和 fast 之间的距离为 n
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 同时移动 slow 和 fast，直到 fast 到达链表末尾
        // 这样，slow 会指向倒数第 n 个节点的前一个节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除倒数第 n 个节点
        slow.next = slow.next.next;

        // 返回删除后的链表头结点
        return dummyNode.next;
    }
}

面试题02.07链表相交

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

图示两个链表在节点 c1 开始相交：

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

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

示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 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]

进阶： 你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

原理

这段代码的目标是找出两个单链表的交点。如果两个链表有交点，返回交点的节点；如果没有交点，返回 null 。

思路：

计算链表的长度 ：

首先，我们遍历两个链表，计算出它们的长度 len1 和 len2 。

这样我们可以知道哪个链表更长。

调整长链表的指针位置 ：

如果链表A的长度大于链表B，那么我们可以让链表A的指针向前移动 len1 - len2 步，这样两个链表的指针在接下来的遍历中将会指向相同的节点。

如果链表B的长度大于链表A，那么我们也可以将链表B的指针向前移动 len2 - len1 步。

同步遍历两个链表 ：

调整指针位置之后，两个链表的剩余部分长度相等，我们可以同步遍历两个链表。

每次比较当前节点是否相等，一旦发现相等的节点，即为交点节点，返回该节点。

如果没有交点 ：

如果两个链表在遍历过程中没有发现相同的节点，则说明这两个链表没有交点，返回 null 。

举例说明：

假设链表A和链表B分别为：

链表A：[4, 1, 8, 4, 5]

链表B：[5, 0, 1, 8, 4, 5]

len1 = 5， len2 = 6

由于链表B更长，我们把链表B的指针移动1步，变成：

链表A：[4, 1, 8, 4, 5]

链表B：[0, 1, 8, 4, 5]

然后同步遍历两个链表，发现第一个交点是在节点 8。

复杂度分析：

时间复杂度 ：O(m + n)，其中 m 和 n 分别是链表A和链表B的长度。我们需要遍历两次链表，一次计算长度，一次同步遍历。

空间复杂度 ：O(1)，我们只使用了常数的额外空间，不会随链表长度增长。

代码

public class Solution {
    // 主方法：获取两个链表的交点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 记录链表A和链表B的长度
        int len1 = 0, len2 = 0;
        
        // 创建虚拟头结点以方便操作
        ListNode dumyNode1 = new ListNode(-1);
        ListNode dumyNode2 = new ListNode(-1);
        dumyNode1.next = headA;
        dumyNode2.next = headB;
        
        // 计算链表A的长度
        ListNode cur1 = dumyNode1;
        while (cur1.next != null) {
            cur1 = cur1.next;
            len1++;
        }
        
        // 计算链表B的长度
        ListNode cur2 = dumyNode2;
        while (cur2.next != null) {
            cur2 = cur2.next;
            len2++;
        }

        // 如果链表A的长度大于链表B，交换两个链表，使得链表A较短
        if (len1 >= len2) {
            return getNode(headA, headB, len1, len2);
        } else {
            return getNode(headB, headA, len2, len1);
        }
    }

    // 辅助方法：将长度较长的链表指针往前移动，直到两个链表指针等长
    public ListNode getNode(ListNode headA, ListNode headB, int len1, int len2) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;

        // 将长链表的指针移动到与短链表对齐
        for (int i = 0; i < (len1 - len2); i++) {
            cur1 = cur1.next;
        }

        // 同步遍历两个链表，找到第一个相同的节点
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) {
                return cur1;  // 找到交点
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        // 如果没有交点，返回null
        return null;
    }
}

142.环形链表II

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

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

不允许修改 链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：

链表中节点的数目范围在范围 [0, 104] 内

-105 <= Node.val <= 105

pos 的值为 -1 或者链表中的一个有效索引

进阶： 你是否可以使用 O(1) 空间解决此题？

原理

这段代码的目的是检测链表是否存在环，并返回入环的第一个节点。如果链表没有环，则返回 null 。解决方案使用了 快慢指针 （Floyd's Cycle Detection Algorithm）的方法，具体步骤如下：

1. 初始化两个指针：

慢指针 slow ：每次走一步。

快指针 fast ：每次走两步。

2. 快慢指针的移动：

快指针 fast 和慢指针 slow 同时从链表头开始遍历。

每次， slow 前进一步， fast 前进两步。

如果链表中存在环，则快指针 fast 和慢指针 slow 必定会在环中相遇。

3. 相遇判断：

当 slow == fast 时，表明链表存在环，因为快指针追上了慢指针。

4. 找到环的起始节点：

一旦发现快慢指针相遇，就表示链表中有环。此时，我们将一个指针（可以是 fast 或者 head ）重新指向链表头部，另一个指针保持在相遇点。

然后两个指针每次都走一步，直到它们再次相遇。这时，它们相遇的节点即为链表中的环的起始节点。

5. 如果链表没有环：

如果 fast 或 fast.next 为 null ，说明链表没有环，直接返回 null 。

举例说明：

假设链表为：[3, 2, 0, -4]，并且链表尾部连接到第二个节点（即节点 2），我们将通过快慢指针检测环。

初始化时， slow 和 fast 都指向链表的头节点（值为 3）。

第一次迭代：

slow 移动到节点 2（走一步）。

fast 移动到节点 0（走两步）。

第二次迭代：

slow 移动到节点 0。

fast 移动到节点 2。

第三次迭代：

slow 移动到节点 -4。

fast 移动到节点 -4。

此时 slow == fast ，说明快慢指针相遇，链表中有环。

接着，指针 index1 被重置为相遇点（即 -4），指针 index2 被重置为链表头（即 3），然后两个指针每次向前走一步：

第一次迭代：

index1 移动到节点 3， index2 移动到节点 2。

第二次迭代：

index1 移动到节点 2， index2 移动到节点 2。

结果发现， index1 和 index2 相遇，返回节点 2，表示链表的入环节点。

复杂度分析：

时间复杂度 ：O(n)，其中 n 是链表中的节点数。我们最多需要遍历两次链表：第一次是快慢指针相遇，第二次是从头开始找入环节点。

空间复杂度 ：O(1)，只使用了常数的额外空间。

代码

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) {
                // 相遇时，将fast指针重置为head，继续寻找入环点
                ListNode index1 = fast;
                ListNode index2 = head;

                // 移动两个指针，直到它们相遇时，即为入环节点
                while (index1 != index2) {
                    index1 = index1.next;  // 指针1步进
                    index2 = index2.next;  // 指针2步进
                }

                // 返回入环节点
                return index1;
            }
        }

        // 如果没有环，返回null
        return null;
    }
}

抖音发布助手(手机版)

模板安装包

快手【自动发布】【手机版】

快手养号功能

域名采集筛选工具

leetcode——链表

206.反转链表

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

面试题02.07链表相交

142.环形链表II