线性数据结构的原理与应用
| 特性 | 数组（Array） | 链表（Linked List） |
|---|---|---|
| 内存分配 | 连续内存空间 | 非连续内存空间 |
| 随机访问 | O(1) - 支持下标访问 | O(n) - 需要遍历 |
| 插入/删除 | O(n) - 需要移动元素 | O(1) - 只需修改指针 |
| 内存利用 | 紧凑，无额外开销 | 需要额外存储指针 |
| 缓存友好 | 是 - 连续内存 | 否 - 内存分散 |
| 大小 | 固定或需要扩容 | 动态增长 |
| 操作 | 数组 | 链表 |
|---|---|---|
| 访问第i个元素 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | O(1)* | O(n) 或 O(1)** |
| 中间插入 | O(n) | O(n) |
| 查找元素 | O(n) | O(n) |
* 动态数组可能需要扩容
** 双向链表维护尾指针可O(1)
public class MyArrayList {
private Object[] elements;
private int size;
private static final int DEFAULT_CAPACITY = 10;
public MyArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public void add(E element) {
ensureCapacity();
elements[size++] = element;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return (E) elements[index];
}
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 将后面的元素前移
System.arraycopy(elements, index + 1, elements, index, size - index - 1);
elements[--size] = null; // 帮助GC
}
private void ensureCapacity() {
if (size == elements.length) {
int newCapacity = elements.length * 2;
elements = Arrays.copyOf(elements, newCapacity);
}
}
public int size() {
return size;
}
} 如果每次只扩容1个，插入n个元素需要拷贝1+2+3+...+n = O(n²)次。扩容为2倍时，总拷贝次数为O(n)，均摊时间复杂度为O(1)。
给定单链表的头节点head，反转链表并返回反转后的链表。
示例：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; // prev是新的头节点
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next); // 递归反转后面的链表
head.next.next = head; // 让下一个节点指向当前节点
head.next = null; // 断开当前节点的next
return newHead;
}
// 时间复杂度：O(n)
// 空间复杂度：O(n) - 递归栈初始：1 → 2 → 3 → null 步骤1：null ← 1 2 → 3 → null 步骤2：null ← 1 ← 2 3 → null 步骤3：null ← 1 ← 2 ← 3
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; // 慢指针走1步
fast = fast.next.next; // 快指针走2步
if (slow == fast) { // 相遇说明有环
return true;
}
}
return false;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)如果有环，快指针最终会追上慢指针。每次循环，快指针与慢指针的距离减1，所以一定会相遇。
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
// 1. 判断是否有环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 2. 找到环的入口
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}设链表头到环入口距离为a，环入口到相遇点距离为b，环长为c。
相遇时：慢指针走了a+b，快指针走了a+b+nc（n圈）
因为快指针速度是慢指针2倍：2(a+b) = a+b+nc
得：a = nc - b = (n-1)c + (c-b)
所以从头和相遇点同时出发，会在环入口相遇。
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;
}
// 时间复杂度：O(m + n)
// 空间复杂度：O(1)public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
// 时间复杂度：O(m + n)
// 空间复杂度：O(m + n) - 递归栈使用哨兵节点（dummy node）可以简化边界条件处理，避免特殊判断头节点。
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // slow指向中间节点
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)快指针每次走2步，慢指针每次走1步。当快指针到达末尾时，慢指针正好在中间。
找中间节点常用于链表的归并排序、判断回文链表等问题。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// first先走n+1步
for (int i = 0; i <= n; i++) {
first = first.next;
}
// first和second一起走，直到first到末尾
while (first != null) {
first = first.next;
second = second.next;
}
// 删除second的下一个节点
second.next = second.next.next;
return dummy.next;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)因为我们需要找到倒数第n个节点的前一个节点，这样才能删除它。
如果要删除的是头节点，使用dummy可以统一处理，避免特殊判断。
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 1. 找到中间节点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 反转后半部分链表
ListNode secondHalf = reverseList(slow.next);
// 3. 比较前半部分和反转后的后半部分
ListNode p1 = head, p2 = secondHalf;
boolean result = true;
while (p2 != null) {
if (p1.val != p2.val) {
result = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
// 4. 恢复链表（可选）
slow.next = reverseList(secondHalf);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)public boolean isPalindrome(ListNode head) {
Stack stack = new Stack<>();
ListNode curr = head;
// 将所有值压入栈
while (curr != null) {
stack.push(curr.val);
curr = curr.next;
}
// 比较
curr = head;
while (curr != null) {
if (curr.val != stack.pop()) {
return false;
}
curr = curr.next;
}
return true;
} public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
// 最小堆
PriorityQueue pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// 将所有链表的头节点加入堆
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
curr.next = node;
curr = curr.next;
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}
// 时间复杂度：O(N log k)，N是所有节点总数，k是链表数量
// 空间复杂度：O(k) public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
if (left == right) {
return lists[left];
}
int mid = left + (right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
// 时间复杂度：O(N log k)
// 空间复杂度：O(log k) - 递归栈跳表是一种基于有序链表的数据结构，通过在链表上建立多级索引来加速查找。
Level 3: 1 -----------------> 7 Level 2: 1 ------> 4 ------> 7 ------> 10 Level 1: 1 -> 3 -> 4 -> 6 -> 7 -> 9 -> 10 Level 0: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
| 特性 | 跳表 | 红黑树 |
|---|---|---|
| 实现复杂度 | 简单 | 复杂 |
| 查找效率 | O(log n) | O(log n) |
| 范围查询 | 简单高效 | 需要中序遍历 |
| 并发性 | 容易实现无锁 | 困难 |
class SkipListNode {
int val;
SkipListNode[] next; // 每层的下一个节点
public SkipListNode(int val, int level) {
this.val = val;
this.next = new SkipListNode[level];
}
}class SkipList {
private static final int MAX_LEVEL = 16;
private static final double P = 0.5; // 晋升概率
private SkipListNode head;
private int level;
public SkipList() {
head = new SkipListNode(Integer.MIN_VALUE, MAX_LEVEL);
level = 0;
}
// 查找
public boolean search(int target) {
SkipListNode curr = head;
for (int i = level; i >= 0; i--) {
while (curr.next[i] != null && curr.next[i].val < target) {
curr = curr.next[i];
}
}
curr = curr.next[0];
return curr != null && curr.val == target;
}
// 插入
public void add(int num) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL];
SkipListNode curr = head;
// 找到每层的插入位置
for (int i = level; i >= 0; i--) {
while (curr.next[i] != null && curr.next[i].val < num) {
curr = curr.next[i];
}
update[i] = curr;
}
// 随机生成层数
int newLevel = randomLevel();
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = head;
}
level = newLevel;
}
// 插入节点
SkipListNode newNode = new SkipListNode(num, newLevel + 1);
for (int i = 0; i <= newLevel; i++) {
newNode.next[i] = update[i].next[i];
update[i].next[i] = newNode;
}
}
// 删除
public boolean erase(int num) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL];
SkipListNode curr = head;
for (int i = level; i >= 0; i--) {
while (curr.next[i] != null && curr.next[i].val < num) {
curr = curr.next[i];
}
update[i] = curr;
}
curr = curr.next[0];
if (curr == null || curr.val != num) {
return false;
}
// 删除节点
for (int i = 0; i <= level; i++) {
if (update[i].next[i] != curr) {
break;
}
update[i].next[i] = curr.next[i];
}
// 更新level
while (level > 0 && head.next[level] == null) {
level--;
}
return true;
}
private int randomLevel() {
int lvl = 0;
while (Math.random() < P && lvl < MAX_LEVEL - 1) {
lvl++;
}
return lvl;
}
}通过随机决定节点的层数，可以保持跳表的平衡性，避免退化为链表。概率P通常设为0.5或0.25。
使用哈希表 + 双向链表实现O(1)的get和put操作。
class LRUCache {
class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
private Map map;
private Node head, tail;
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
remove(node);
addToHead(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
remove(node);
addToHead(node);
} else {
if (map.size() == capacity) {
map.remove(tail.prev.key);
remove(tail.prev);
}
Node node = new Node(key, value);
map.put(key, node);
addToHead(node);
}
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}
// 时间复杂度：O(1)
// 空间复杂度：O(capacity) 双向链表可以O(1)删除节点（需要知道前驱节点），单向链表需要O(n)。
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 1. 找到中间节点
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 分割链表
ListNode mid = slow.next;
slow.next = null;
// 3. 递归排序
ListNode left = sortList(head);
ListNode right = sortList(mid);
// 4. 合并
return merge(left, right);
}
private ListNode merge(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;
}
// 时间复杂度：O(n log n)
// 空间复杂度：O(log n) - 递归栈快速排序需要随机访问，链表不支持O(1)随机访问，效率低。归并排序只需要顺序访问，更适合链表。
给定链表，将链表向右旋转k个位置。
示例：1→2→3→4→5，k=2 变为 4→5→1→2→3
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// 1. 计算链表长度并连成环
ListNode tail = head;
int len = 1;
while (tail.next != null) {
tail = tail.next;
len++;
}
tail.next = head; // 连成环
// 2. 找到新的尾节点（第 len - k % len 个节点）
k = k % len;
int stepsToNewTail = len - k;
ListNode newTail = head;
for (int i = 1; i < stepsToNewTail; i++) {
newTail = newTail.next;
}
// 3. 断开环
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)链表节点包含next和random指针，random可能指向链表中任意节点或null。要求深拷贝链表。
public Node copyRandomList(Node head) {
if (head == null) return null;
Map map = new HashMap<>();
// 第一遍：复制所有节点
Node curr = head;
while (curr != null) {
map.put(curr, new Node(curr.val));
curr = curr.next;
}
// 第二遍：设置next和random指针
curr = head;
while (curr != null) {
map.get(curr).next = map.get(curr.next);
map.get(curr).random = map.get(curr.random);
curr = curr.next;
}
return map.get(head);
}
// 时间复杂度：O(n)
// 空间复杂度：O(n) public Node copyRandomList(Node head) {
if (head == null) return null;
// 1. 在每个节点后插入复制节点
Node curr = head;
while (curr != null) {
Node copy = new Node(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}
// 2. 设置random指针
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// 3. 分离两个链表
Node dummy = new Node(0);
Node copyCurr = dummy;
curr = head;
while (curr != null) {
copyCurr.next = curr.next;
curr.next = curr.next.next;
curr = curr.next;
copyCurr = copyCurr.next;
}
return dummy.next;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)原链表：A → B → C 步骤1：A → A' → B → B' → C → C' 步骤2：设置A'.random, B'.random, C'.random 步骤3：分离为 A → B → C 和 A' → B' → C'