返回题库算法与数据结构刷题链表 · 第 3 / 3 篇

算法编程题：链表（7 题）

链表·7 道编程题#算法#C##面试#刷题#编程题#链表

025 原地反转单链表并返回新的头节点。

难度： 基础

方法签名： ListNode? head

输入约束： 链表无环

示例： 1→2→3 → 3→2→1

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 维护 previous、current 和 next，逐个改写 Next。

不变量： previous 指向已经反转的前缀，current 指向未处理后缀首节点。

public static class AlgCode025Solution
{
    public sealed class ListNode
    {
        public int Value;
        public ListNode? Next;
        public ListNode(int value, ListNode? next = null)
            => (Value, Next) = (value, next);
    }
    
    public static ListNode? Solve(ListNode? head)
    {
        ListNode? previous = null;
        ListNode? current = head;
        while (current is not null)
        {
            ListNode? next = current.Next;
            current.Next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 空链表；单节点；两个节点。

面试追问：

  • 递归反转的调用栈空间是多少？

026 复用原节点合并两个升序单链表。

难度： 进阶

方法签名： ListNode? first, ListNode? second

输入约束： 两条链表无环且按 Value 非降序

示例： 1→3 与 2→4 → 1→2→3→4

目标复杂度： 时间 O(n+m)，额外空间 O(1)

查看参考答案

解题思路： 使用虚拟头节点，每次连接较小的当前节点。

不变量： tail 之前是已经合并的有序前缀，两个输入指针指向未处理后缀。

public static class AlgCode026Solution
{
    public sealed class ListNode
    {
        public int Value;
        public ListNode? Next;
        public ListNode(int value, ListNode? next = null)
            => (Value, Next) = (value, next);
    }
    
    public static ListNode? Solve(ListNode? first, ListNode? second)
    {
        var sentinel = new ListNode(0);
        ListNode tail = sentinel;
        while (first is not null && second is not null)
        {
            if (first.Value <= second.Value)
            {
                tail.Next = first;
                first = first.Next;
            }
            else
            {
                tail.Next = second;
                second = second.Next;
            }
            tail = tail.Next;
        }
        tail.Next = first ?? second;
        return sentinel.Next;
    }
}

复杂度： 时间 O(n+m)，额外空间 O(1)。

边界用例： 任一链表为空；重复值；长度差异很大。

面试追问：

  • 合并 K 条链表时如何利用优先队列？

027 使用 O(1) 额外空间检测单链表是否存在环。

难度： 进阶

方法签名： ListNode? head

输入约束： 节点数有限，Next 可能形成环

示例： 3→2→0→-4，尾节点指向值为 2 的节点 → true

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 快指针每次两步，慢指针每次一步，有环时必在环内相遇。

不变量： 无环时 fast 最终到达 null；有环时二者距离按模环长变化。

public static class AlgCode027Solution
{
    public sealed class ListNode
    {
        public int Value;
        public ListNode? Next;
        public ListNode(int value) => Value = value;
    }
    
    public static bool Solve(ListNode? head)
    {
        ListNode? slow = head;
        ListNode? fast = head;
        while (fast is not null && fast.Next is not null)
        {
            slow = slow!.Next;
            fast = fast.Next.Next;
            if (ReferenceEquals(slow, fast)) return true;
        }
        return false;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 空链表；单节点自环；无环长链。

面试追问：

  • 如何在检测到环后找到入环节点？

028 返回单链表的中间节点，偶数长度时返回后一个中点。

难度： 基础

方法签名： ListNode? head

输入约束： 链表无环

示例： 1→2→3→4 → 节点 3

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 慢指针一步、快指针两步，快指针结束时慢指针位于中点。

不变量： slow 走过的节点数约为 fast 的一半。

public static class AlgCode028Solution
{
    public sealed class ListNode
    {
        public int Value;
        public ListNode? Next;
        public ListNode(int value, ListNode? next = null)
            => (Value, Next) = (value, next);
    }
    
    public static ListNode? Solve(ListNode? head)
    {
        ListNode? slow = head;
        ListNode? fast = head;
        while (fast is not null && fast.Next is not null)
        {
            slow = slow!.Next;
            fast = fast.Next.Next;
        }
        return slow;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 空链表；单节点；奇数与偶数长度。

面试追问：

  • 如何调整初始化以返回偶数长度时的前一个中点？

029 一次扫描删除单链表倒数第 N 个节点。

难度： 进阶

方法签名： ListNode? head, int n

输入约束： 1 <= n <= 链表长度

示例： 1→2→3→4→5, n=2 → 1→2→3→5

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 让 fast 先走 n 步，再同步移动 fast 与 slow 到目标前驱。

不变量： fast 与 slow 之间始终保持 n 个节点的距离。

public static class AlgCode029Solution
{
    public sealed class ListNode
    {
        public int Value;
        public ListNode? Next;
        public ListNode(int value, ListNode? next = null)
            => (Value, Next) = (value, next);
    }
    
    public static ListNode? Solve(ListNode? head, int n)
    {
        var sentinel = new ListNode(0, head);
        ListNode? fast = sentinel;
        for (int step = 0; step < n; step++) fast = fast!.Next;
        ListNode slow = sentinel;
        while (fast!.Next is not null)
        {
            fast = fast.Next;
            slow = slow.Next!;
        }
        slow.Next = slow.Next!.Next;
        return sentinel.Next;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 删除头节点；删除尾节点；单节点链表。

面试追问：

  • 如果 n 可能非法，如何在不额外扫描的前提下返回失败？

030 返回两条可能相交的无环单链表的第一个公共节点。

难度： 进阶

方法签名： ListNode? first, ListNode? second

输入约束： 两条链表无环，相交后共享同一节点后缀

示例： A:1→8→9，B:2→3→8→9 → 共享节点 8

目标复杂度： 时间 O(n+m)，额外空间 O(1)

查看参考答案

解题思路： 两个指针到达末尾后切换到另一条链表头，抵消长度差。

不变量： 两个指针走过相同总距离后会同时到达交点或 null。

public static class AlgCode030Solution
{
    public sealed class ListNode
    {
        public int Value;
        public ListNode? Next;
        public ListNode(int value) => Value = value;
    }
    
    public static ListNode? Solve(ListNode? first, ListNode? second)
    {
        ListNode? left = first;
        ListNode? right = second;
        while (!ReferenceEquals(left, right))
        {
            left = left is null ? second : left.Next;
            right = right is null ? first : right.Next;
        }
        return left;
    }
}

复杂度： 时间 O(n+m)，额外空间 O(1)。

边界用例： 任一为空；头节点即相交；值相同但节点不同；不相交。

面试追问：

  • 如果链表可能有环，问题需要先区分哪些情况？

031 深拷贝带随机指针的单链表。

难度： 综合

方法签名： RandomNode? head

输入约束： Next 无环，Random 可指向任意节点或 null

示例： 复制后结构和值相同，但所有节点引用独立

目标复杂度： 平均时间 O(n)，额外空间 O(n)

查看参考答案

解题思路： 第一遍创建原节点到副本的映射，第二遍连接 Next 与 Random。

不变量： 映射中的每个原节点都对应唯一的新节点。

public static class AlgCode031Solution
{
    public sealed class RandomNode
    {
        public int Value;
        public RandomNode? Next;
        public RandomNode? Random;
        public RandomNode(int value) => Value = value;
    }
    
    public static RandomNode? Solve(RandomNode? head)
    {
        if (head is null) return null;
        var copies = new Dictionary<RandomNode, RandomNode>();
        for (RandomNode? node = head; node is not null; node = node.Next)
            copies[node] = new RandomNode(node.Value);
        for (RandomNode? node = head; node is not null; node = node.Next)
        {
            RandomNode copy = copies[node];
            copy.Next = node.Next is null ? null : copies[node.Next];
            copy.Random = node.Random is null ? null : copies[node.Random];
        }
        return copies[head];
    }
}

复杂度： 平均时间 O(n)，额外空间 O(n)。

边界用例： 空链表；Random 指向自身；多个节点指向同一节点。

面试追问：

  • 如何通过把副本节点穿插到原链表中把额外空间降为 O(1)？
当前分类

链表

查看全部分类 →
  1. 01算法专题：链表
  2. 02算法选择题：链表（5 题）5 题
  3. 03算法编程题：链表（7 题）7 题
ESC

输入关键词开始搜索