IT面试题|麻瓜面试

Appearance

链表 ​

链表是一种基础的数据结构，其特点是节点通过指针串联，不支持随机访问。面试中链表题目通常考察指针操作的细节，如反转、合并、环检测等。掌握虚拟头节点、快慢指针、多指针联动等技巧，能让你在链表题中游刃有余。

Q1: 反转链表 「🟢 初级」 ​

题目描述：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

考察点：链表指针操作、递归与迭代、虚拟头节点。

解题思路：

  • 方法1：迭代法，三指针 prev/curr/next 逐个反转（时间O(n)，空间O(1)）- 最优解
  • 方法2：递归法，先递归到尾部再逐层反转（时间O(n)，空间O(n)栈空间）

代码实现：

java
// 迭代法
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

复杂度分析：时间复杂度 O(n)，遍历一次链表；空间复杂度 O(1)，仅使用常数额外指针。

变体扩展：

  • 变体1：反转链表II（反转指定区间）
  • 变体2：K个一组翻转链表
  • 变体3：两两交换链表中的节点
  • 变体4：回文链表

Q2: 合并两个有序链表 「🟢 初级」 ​

题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

考察点：链表的归并操作、虚拟头节点技巧、递归思路。

解题思路：

  • 方法1：迭代法，使用虚拟头节点串联（时间O(n+m)，空间O(1)）- 最优解
  • 方法2：递归法（时间O(n+m)，空间O(n+m)栈空间）

代码实现：

java
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    curr.next = (list1 != null) ? list1 : list2;
    return dummy.next;
}

复杂度分析：时间复杂度 O(n+m)，最多遍历两个链表各一次；空间复杂度 O(1)，仅使用虚拟头节点。

变体扩展：

  • 变体1：合并k个升序链表
  • 变体2：合并两个有序数组
  • 变体3：排序链表（归并排序思路）

Q3: 环形链表 「🟢 初级」 ​

题目描述：给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

考察点：快慢指针（Floyd判圈算法）、哈希表。

解题思路：

  • 方法1：哈希表，存储已访问节点（时间O(n)，空间O(n)）
  • 方法2：快慢指针，fast走两步，slow走一步，相遇则有环（时间O(n)，空间O(1)）- 最优解

代码实现：

java
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;
}

复杂度分析：时间复杂度 O(n)，有环时fast在环内追上slow最多需要n步；空间复杂度 O(1)。

变体扩展：

  • 变体1：环形链表II（找到环的入口）
  • 变体2：快乐数
  • 变体3：寻找重复数
  • 变体4：相交链表

Q4: 环形链表II 「🟡 中级」 ​

题目描述：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。不允许修改给定的链表。

考察点：快慢指针数学推导、环的入口定位。

解题思路：

  • 方法1：哈希表（时间O(n)，空间O(n)）
  • 方法2：快慢指针 + 数学推导，相遇后一个指针从头开始，两指针同速前进，再次相遇即为入口（时间O(n)，空间O(1)）- 最优解

代码实现：

java
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 ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
}

复杂度分析：时间复杂度 O(n)，快慢指针相遇后再走到入口不超过n步；空间复杂度 O(1)。

变体扩展：

  • 变体1：环形链表（判断是否有环）
  • 变体2：寻找重复数
  • 变体3：快乐数

Q5: 链表中倒数第k个节点 「🟢 初级」 ​

题目描述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

考察点：快慢指针、一次遍历技巧。

解题思路：

  • 方法1：两次遍历，先求长度再找第n-k+1个节点（时间O(n)，空间O(1)）
  • 方法2：快慢指针，fast先走k步，然后同速前进，fast到末尾时slow即为倒数第k个（时间O(n)，空间O(1)）- 最优解

代码实现：

java
public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast = head;
    ListNode slow = head;
    for (int i = 0; i < k; i++) {
        if (fast == null) return null;
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

复杂度分析：时间复杂度 O(n)，一次遍历；空间复杂度 O(1)。

变体扩展：

  • 变体1：删除链表的倒数第N个节点
  • 变体2：旋转链表
  • 变体3：中间节点（快慢指针变体）

Q6: 两两交换链表中的节点 「🟡 中级」 ​

题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换）。

考察点：多指针操作、递归与迭代、虚拟头节点。

解题思路：

  • 方法1：迭代法，使用虚拟头节点和多指针（时间O(n)，空间O(1)）- 最优解
  • 方法2：递归法（时间O(n)，空间O(n)栈空间）

代码实现：

java
public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next;
        ListNode second = prev.next.next;
        first.next = second.next;
        second.next = first;
        prev.next = second;
        prev = first;
    }
    return dummy.next;
}

复杂度分析：时间复杂度 O(n)，每个节点被访问一次；空间复杂度 O(1)。

变体扩展：

  • 变体1：K个一组翻转链表
  • 变体2：反转链表
  • 变体3：重排链表

Q7: 重排链表 「🟡 中级」 ​

题目描述：给定一个单链表 L 的头节点 head，单链表 L 表示为：L0 → L1 → … → Ln-1 → Ln。请将其重新排列后变为：L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …。不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

考察点：链表综合题（找中点 + 反转 + 合并）、快慢指针。

解题思路：

  • 方法1：数组存储 + 双指针重建（时间O(n)，空间O(n)）
  • 方法2：快慢指针找中点 → 反转后半段 → 交替合并（时间O(n)，空间O(1)）- 最优解

代码实现：

java
public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    // 1. 快慢指针找中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. 反转后半段
    ListNode second = reverse(slow.next);
    slow.next = null;
    // 3. 交替合并
    ListNode first = head;
    while (second != null) {
        ListNode next1 = first.next;
        ListNode next2 = second.next;
        first.next = second;
        second.next = next1;
        first = next1;
        second = next2;
    }
}

private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

复杂度分析：时间复杂度 O(n)，三次线性遍历；空间复杂度 O(1)，原地操作。

变体扩展：

  • 变体1：回文链表
  • 变体2：K个一组翻转链表
  • 变体3：排序链表

Q8: LRU缓存机制 「🔴 高级」 ​

题目描述：请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

考察点：哈希表 + 双向链表、数据结构设计、最近最少使用策略。

解题思路：

  • 方法：哈希表 + 双向链表。哈希表实现O(1)查找，双向链表维护使用顺序（时间O(1) get/put，空间O(capacity)）- 最优解

代码实现：

java
class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;
    
    public LRUCache(int capacity) {
        this.size = 0;
        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) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
    
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

复杂度分析：get 和 put 操作时间复杂度均为 O(1)；空间复杂度 O(capacity)，哈希表和双向链表各存 capacity 个节点。

变体扩展：

  • 变体1：LFU缓存
  • 变体2：设计循环双端队列
  • 变体3：全 O(1) 的数据结构

Copyright © 2025-2026 京公网安备 11010102000001号 京ICP备2024078125号-1