当前位置：首页 > news >正文

深入理解链表：从基础操作到高频面试题解析

news 2025/4/29 7:20:27

一、链表基础概念

1.1 什么是链表？

1.2 链表核心特性

1.3 链表与数组对比

二、链表类型详解

2.1 单向链表

2.2 双向链表

2.3 循环链表

三、链表核心操作实现

3.1 插入操作

3.2 删除操作

四、链表高频面试题精讲

4.1 反转链表（LeetCode 206）

4.2 环形链表检测（LeetCode 141）

4.3 合并有序链表（LeetCode 21）

五、链表实战技巧

5.1 边界条件处理

5.2 调试技巧

5.3 性能优化

六、常见问题解答

一、链表基础概念

1.1 什么是链表？

链表（Linked List）是一种物理存储结构上非连续的线性数据结构。不同于数组需要连续内存空间，链表通过节点（Node）之间的引用（指针）实现逻辑上的连续性。每个节点包含两部分：数据域（存储数据）和指针域（指向下一节点）

1.2 链表核心特性

访问时间复杂度：O(n)（不支持随机访问）
插入/删除优势：O(1)时间复杂度（在已知位置时）
适用场景：频繁插入删除、无需预知数据规模

1.3 链表与数组对比

特性	链表	数组
内存空间	动态分配，无需连续	需要连续内存
插入/删除效率	O(1)（已知位置）	O(n)
访问效率	O(n)	O(1)
空间利用率	每个节点额外存储指针空间	无额外空间开销

二、链表类型详解

2.1 单向链表

结构特点：

每个节点包含数据域和指向下一节点的指针
首节点称为头节点（Head），末节点指针指向null

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

2.2 双向链表

结构优势：

每个节点包含前驱和后继指针
支持双向遍历，提升特定操作效率

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

2.3 循环链表

核心特征：

尾节点指针指向头节点形成闭环
适合需要循环访问的场景（如轮询任务）

三、链表核心操作实现

3.1 插入操作

头插法（时间复杂度O(1)）：

public void addFirst(int val) {ListNode newNode = new ListNode(val);newNode.next = head;head = newNode;
}

尾插法（时间复杂度O(n)）：

public void addLast(int val) {ListNode newNode = new ListNode(val);if (head == null) {head = newNode;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = newNode;
}

3.2 删除操作

删除指定值节点：

public void remove(int key) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode prev = dummy;while (prev.next != null) {if (prev.next.val == key) {prev.next = prev.next.next;} else {prev = prev.next;}}head = dummy.next;
}

四、链表高频面试题精讲

4.1 反转链表（LeetCode 206）

核心思路：三指针法

维护前驱指针prev、当前指针curr、后继指针next
逐个节点反转指针方向

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

4.2 环形链表检测（LeetCode 141）

快慢指针法：

快指针每次走两步，慢指针每次走一步
若相遇则存在环，时间复杂度O(n)

public boolean hasCycle(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) return true;}return false;
}

4.3 合并有序链表（LeetCode 21）

双指针技巧：

创建哑节点作为新链表头部
比较两链表节点值，按序连接

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