跳到主要内容

链表

问题​

链表相关的高频面试题有哪些？

答案​

链表节点定义​

public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

1. 反转链表（必会）​

迭代法反转
public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;  // 暂存下一个
        curr.next = prev;           // 反转指向
        prev = curr;                // prev 前进
        curr = next;                // curr 前进
    }
    return prev;
}

2. 判断链表有环​

快慢指针判环
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;        // 慢指针走 1 步
        fast = fast.next.next;   // 快指针走 2 步
        if (slow == fast) return true;  // 相遇则有环
    }
    return false;
}

3. 找环的入口​

找环入口节点
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 快慢指针相遇后，一个从 head 出发，一个从相遇点出发
            // 两者再次相遇的地方就是环入口
            ListNode p = head;
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
    }
    return null;
}

4. 合并两个有序链表​

迭代合并
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);  // 哨兵节点
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

5. 删除倒数第 N 个节点​

双指针间隔 N 步
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    // fast 先走 n+1 步
    for (int i = 0; i <= n; i++) fast = fast.next;
    // 同步前进，fast 到末尾时 slow 到倒数第 n+1 个
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;  // 删除
    return dummy.next;
}

常见面试问题​

Q1: 链表和数组的区别？​

答案：

维度数组链表
内存布局连续不连续
随机访问O(1)O(1)O(n)O(n)
插入/删除O(n)O(n)（移动元素）O(1)O(1)（已知位置）
缓存友好✅❌

Java 中 ArrayList 基于数组，LinkedList 基于双向链表。大多数场景推荐 ArrayList（缓存友好、随机访问快）。

Q2: 什么是哨兵节点（dummy node）？​

答案：

在链表头部加一个虚拟节点（dummy），避免处理头节点为空的边界情况。最后返回 dummy.next。合并链表、删除节点等操作中常用。

相关链接​