数组与链表高频题型 - 算法 | 炼金塔

数组与链表高频题型

一、引入背景

1.1 为什么要学习数组与链表？

工程应用广泛：几乎所有业务系统都会用到数组和链表结构
面试必考内容：手撕代码题中占比超过 30%
思维训练基础：理解底层存储方式是学习其他复杂数据结构的前提

1.2 实际业务场景痛点

场景	痛点	解决方案
电商订单管理	订单数据频繁增删	链表/跳表
缓存淘汰策略	内存空间有限	LRU 缓存
排行榜实现	高并发排名更新	链表 + 哈希
消息队列	消息顺序处理	队列结构

1.3 面试中的重要性

数组：考察对内存连续性的理解、边界处理能力
链表：考察指针操作、递归思维、边界条件处理
综合：快慢指针、双指针技巧是进阶题目的基础

二、核心概念

2.1 数组（Array）

定义：一段连续分配的内存空间，用于存储相同类型的元素。

原理：

内存地址计算：addr[i] = base_addr + i * element_size
支持随机访问，时间复杂度 O(1)
插入/删除需要移动元素，时间复杂度 O(n)

2.2 链表（Linked List）

定义：由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

原理：

节点结构：{ value, next }（单链表）或 { value, prev, next }（双链表）
插入/删除只需修改指针，时间复杂度 O(1)
访问需要遍历，时间复杂度 O(n)

2.3 双指针技巧

定义：使用两个指针协同工作解决特定问题的技巧。

核心分类：

快慢指针：速度不同，用于检测环、找中点
对撞指针：两端向中间逼近，用于有序数组查找
滑动窗口：固定或可变大小的窗口，用于子串问题

三、深度原理

3.1 数组与链表的内存模型

数组内存模型：
┌───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │  ← 连续内存地址
└───┴───┴───┴───┴───┘
  ↓   ↓   ↓   ↓   ↓
[10][20][30][40][50]  ← 实际存储的数据

链表内存模型（分散存储）：
┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐
│ 1 │───▶│ 2 │───▶│ 3 │───▶│ 4 │───▶│ 5 │───▶ null
└───┘    └───┘    └───┘    └───┘    └───┘
 0x10    0x28    0x45    0x67    0x89  ← 随机内存地址

3.2 快慢指针检测环的数学原理

设：

a: 从头到环入口的距离
b: 环入口到相遇点的距离
c: 环的周长

推导过程：

快指针走过的距离 = a + n(b+c) + b
慢指针走过的距离 = a + b

因为快指针速度是慢指针的 2 倍：
2(a+b) = a + n(b+c) + b
a + b = n(b+c)
a = (n-1)(b+c) + c

结论：从头节点出发 a 步 = 从相遇点出发 c 步

四、最佳实践

4.1 使用场景

数据结构	适用场景	不适用场景
数组	频繁随机访问、内存连续性要求高	频繁增删
单链表	频繁增删、无法预知大小	随机访问
双链表	需要双向遍历	内存敏感

4.2 实战技巧

技巧一：哨兵节点（Dummy Node）

作用：简化边界处理，统一操作逻辑
适用：链表头不确定、需统一处理头节点

技巧二：双指针定位

找链表中点：快指针走完时，慢指针在中点
删除倒数第 N 个节点：快指针先走 N 步

技巧三：边界预判

空指针检查
单节点检查
环的存在性检查

1. 反转链表

题目

反转单链表，返回反转后的头节点。

示例

输入: 1 -> 2 -> 3 -> 4 -> 5
输出: 5 -> 4 -> 3 -> 2 -> 1

解法一：迭代

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next; // 保存下一个节点
        curr.next = prev;          // 反转指向
        prev = curr;               // prev 移动到当前节点
        curr = next;               // curr 移动到下一个节点
    }

    return prev;
}

解法二：递归

public ListNode reverseListRec(ListNode head) {
    // 递归终止条件
    if (head == null || head.next == null) {
        return head;
    }

    // 递归反转后续节点
    ListNode newHead = reverseListRec(head.next);

    // 反转当前节点的指向
    head.next.next = head;
    head.next = null;

    return newHead;
}

2. 两数之和

题目

给定一个整数数组 nums 和一个目标值 target，找出和为目标值的两个数的下标。

示例

输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]
解释: nums[0] + nums[1] = 2 + 7 = 9

解法：哈希表

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }

    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

时间：O(n)
空间：O(n)

3. 环形链表检测

题目

判断链表是否有环。

示例

输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表有环，下标 1 的节点指向下标 0

解法：快慢指针

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;         // 慢指针走一步
        fast = fast.next.next;    // 快指针走两步

        if (slow == fast) {       // 相遇，有环
            return true;
        }
    }

    return false;
}

原理：

快慢指针赛跑，如果有环，两者一定会相遇
类似两个人在环形跑道上跑步，跑得快的一定会追上跑得慢的

4. 合并两个有序链表

题目

将两个升序链表合并为一个新的升序链表。

示例

输入: l1 = [1,2,4], l2 = [1,3,4]
输出: [1,1,2,3,4,4]

解法：迭代

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 创建哨兵节点
    ListNode dummy = new ListNode(-1);
    ListNode prev = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }

    // 合并剩余节点
    prev.next = (l1 != null) ? l1 : l2;

    return dummy.next;
}

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

题目

给定一个链表，删除链表的倒数第 n 个节点。

示例

输入: head = [1,2,3,4,5], n = 2
输出: [1,2,3,5]

解法：双指针 + 哑节点

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 创建哑节点，处理边界情况
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode fast = dummy;
    ListNode slow = dummy;

    // 快指针先走 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // 快慢指针同时走
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 删除节点
    slow.next = slow.next.next;

    return dummy.next;
}

6. 链表中环的入口

题目

给定一个链表，返回链表开始入环的第一个节点。

解法：数学推导

public ListNode detectCycle(ListNode head) {
    if (head == null) return null;

    // 1. 检测是否有环
    ListNode slow = head;
    ListNode fast = head;
    boolean hasCycle = false;

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

        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) return null;

    // 2. 找到环的入口
    // 公式：a = (n-1) * (b+c)
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

数学原理：

设：
- a: 从头到环入口的距离
- b: 环入口到相遇点的距离
- c: 环的周长

快指针走过的距离 = a + n(b+c) + b
慢指针走过的距离 = a + b

因为快指针速度是慢指针的 2 倍：
2(a+b) = a + n(b+c) + b
a + b = n(b+c)
a = (n-1)(b+c) + c

所以：从头节点出发 a 步 = 从相遇点出发 c 步

7. 三数之和

题目

找出数组中三个数之和为 0 的所有不重复组合。

示例

输入: nums = [-1, 0, 1, 2, -1, -4]
输出: [[-1, -1, 2], [-1, 0, 1]]

解法：排序 + 双指针

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();

    if (nums == null || nums.length < 3) {
        return result;
    }

    // 排序
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        // 剪枝：跳过重复
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        // 剪枝：最小和大于 0
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;

        // 剪枝：最大和小于 0
        if (nums[i] + nums[nums.length - 2] + nums[nums.length - 1] < 0) continue;

        int target = -nums[i];
        int left = i + 1;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // 跳过重复
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

五、面试突击篇

5.1 基础概念题

Q1: 数组和链表的区别？

🎯 考察重点: 数据结构底层存储原理

📝 回答要点:

存储方式
- 数组：连续内存地址，物理空间连续
- 链表：分散内存地址，通过指针连接
访问时间复杂度
- 数组：O(1)，可直接通过下标计算地址
- 链表：O(n)，需要从头遍历
插入/删除复杂度
- 数组：O(n)，需要移动元素
- 链表：O(1)，只需修改指针
空间特性
- 数组：固定大小，预分配连续空间
- 链表：动态大小，按需分配
缓存友好性
- 数组：友好，CPU 预取机制有效
- 链表：不友好，内存分散

🔍 追问扩展:

Q: 为什么数组查询快但插入删除慢？ A: 数组内存连续，查询只需计算偏移量；插入删除需要移动后续元素保证连续性。
Q: 链表比数组更耗内存吗？ A: 是的，链表需要额外存储指针，且内存碎片化更严重。

5.2 原理分析题

Q2: 快慢指针为什么能检测环？

🎯 考察重点: 数学推导能力、算法理解深度

📝 回答要点:

核心原理
- 快指针每次走 2 步，慢指针每次走 1 步
- 有环时，两者一定会相遇（类似环形跑道追及问题）
数学证明
- 设环长为 C，快指针追上慢指针时，慢指针走了 k 步
- 快指针走了 2k 步，满足：2k - k = nC (n≥1)
- 即 k = nC，一定存在整数解
为什么不能错过？
- 快慢指针相对速度为 1 步/次
- 每一次循环都会缩小距离差

🔍 追问扩展:

Q: 快指针走 3 步可以吗？ A: 可以但不推荐。3 步可能跳过相遇点，2 步是最稳妥的选择。
Q: 如何找环的入口节点？ A: 数学推导可得：从头节点和相遇点同时出发，再次相遇时即为环入口。

5.3 实战应用题

Q3: 如何实现 LRU 缓存？

🎯 考察重点: 数据结构组合设计、代码实现能力

📝 回答要点:

数据结构选择
- 哈希表：O(1) 查询
- 双向链表：O(1) 移动/删除
核心操作
- get(key): 哈希表查找，移动到链表头部
- put(key, value): 哈希表操作，超出容量时删除尾部
实现要点
- 使用双向链表（带哨兵节点）
- 哈希表存储 key -> 链表节点映射
- 容量超限时删除链表尾部节点

class LRUCache {
    private int capacity;
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            node = new DLinkedNode(key, value);
            cache.put(key, node);
            addToHead(node);
            if (cache.size() > capacity) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
}

💡 记忆技巧: LRU = “最近最少使用”，核心思想是”用过的放到最前面”

🔍 追问扩展:

Q: 如何优化到 O(1) 时间复杂度？ A: 使用哈希表 + 双向链表，如上实现。
Q: Redis 中如何实现 LRU？ A: Redis 使用近似 LRU 算法（随机采样 + 淘汰），减少维护成本。

六、总结

6.1 核心要点回顾

知识点	关键点	面试权重
数组	连续内存、O(1) 随机访问	★★★★☆
链表	指针操作、O(1) 增删	★★★★★
双指针	对撞/快慢/滑动窗口	★★★★★
哨兵节点	简化边界处理	★★★☆☆

6.2 学习建议

理解本质：理解数组连续存储和链表离散存储的本质差异
多练手撕：反转链表、合并链表等基础题要能闭眼写
掌握技巧：双指针、哨兵节点是解决复杂问题的基础
数学推导：环形检测等问题的数学原理要能推导

6.3 扩展阅读

《算法导论》第 10 章：基本数据结构
LeetCode 热题 100：数组与链表专题
练习题：21、206、19、142、876、160