目录

  1. 链表基础
  2. 单链表和双链表区别
  3. 链表常用操作
  4. 链表常见技巧与思路
  5. 经典链表算法题解析
  6. 总结与建议

1️⃣ 链表基础

  • 定义：链表是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针（或引用）。
  • 特点：插入删除高效（O(1)），但访问不支持随机索引（访问O(n)）。
  • 类型：
    • 单链表（单向）
    • 双链表（双向）
    • 循环链表（尾部指向头部）

2️⃣ 单链表和双链表区别

特性单链表双链表
指针只有一个指向下一个节点的指针有两个指针，指向前一个和后一个节点
访问方向只能单向访问支持双向访问
内存开销较小较大，因为多一个指针
插入/删除操作需要找到前驱节点插入删除更灵活，常数时间内完成

3️⃣ 链表常用操作

操作说明时间复杂度
遍历访问链表中所有节点O(n)
插入在头部、尾部或中间插入节点头部O(1)，尾部O(n)，有尾指针尾部O(1)
删除删除指定节点或节点值O(n)
查找查找某个值对应的节点O(n)
反转链表反转链表指针方向O(n)

4️⃣ 链表常见技巧与思路

4.1 虚拟头节点（Dummy Head）

  • 用来简化插入和删除边界条件，避免特殊判断头节点情况。

4.2 快慢指针（Floyd判圈法）

  • 用两个指针，一个快一个慢，检测链表中是否有环，或找到链表中点。

4.3 链表反转

  • 三指针法（prev、curr、next）逐步反转链表。

4.4 合并有序链表

  • 归并思想，两个指针逐步比较拼接。

4.5 删除链表倒数第k个节点

  • 双指针法，快指针先走k步，然后快慢指针同时移动。

5️⃣ 经典链表算法题解析

5.1 反转链表（LeetCode 206）

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

5.2 合并两个有序链表（LeetCode 21）

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

5.3 环形链表判定（LeetCode 141）

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

5.4 删除倒数第k个节点（LeetCode 19）

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy, second = dummy;
    for (int i = 0; i <= n; i++) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

6️⃣ 总结与建议

  • 链表操作多依赖指针操作，写代码时要小心空指针和边界条件。
  • 利用虚拟头节点简化边界判断。
  • 掌握快慢指针技巧是链表题目的关键。
  • 多练经典题目，熟悉常见操作模式。