链表

链表是一种非连续存储的线性数据结构，通过指针连接各个节点。

链表的特性

• 非连续存储：节点分散在内存中
• 插入删除高效：不需要移动元素，只需修改指针
• 不支持随机访问：需要从头遍历搜索

单链表

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

public class LinkedList {
    private ListNode head;
    private int size;
    
    public LinkedList() {
        this.head = null;
        this.size = 0;
    }
    
    // 在头部插入 - O(1)
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 在尾部插入 - O(n)
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);
        
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    // 在指定位置插入 - O(n)
    public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        
        if (index == 0) {
            addFirst(val);
            return;
        }
        
        ListNode newNode = new ListNode(val);
        ListNode prev = head;
        
        // 找到前驱节点
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }
    
    // 删除头部 - O(1)
    public int removeFirst() {
        if (head == null) {
            throw new IllegalStateException("List is empty");
        }
        
        int val = head.val;
        head = head.next;
        size--;
        return val;
    }
    
    // 删除指定位置 - O(n)
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        
        if (index == 0) {
            return removeFirst();
        }
        
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        
        int val = prev.next.val;
        prev.next = prev.next.next;
        size--;
        return val;
    }
    
    // 查找 - O(n)
    public int indexOf(int val) {
        ListNode current = head;
        int index = 0;
        
        while (current != null) {
            if (current.val == val) {
                return index;
            }
            current = current.next;
            index++;
        }
        
        return -1;
    }
}

双链表

双链表的每个节点有两个指针，分别指向前驱和后继：

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

public class DoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode tail;
    private int size;
    
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    // 在头部插入 - O(1)
    public void addFirst(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }
    
    // 在尾部插入 - O(1)
    public void addLast(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        
        if (tail == null) {
            head = tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // 删除头部 - O(1)
    public int removeFirst() {
        if (head == null) {
            throw new IllegalStateException("List is empty");
        }
        
        int val = head.val;
        
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        
        size--;
        return val;
    }
    
    // 删除尾部 - O(1)
    public int removeLast() {
        if (tail == null) {
            throw new IllegalStateException("List is empty");
        }
        
        int val = tail.val;
        
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        
        size--;
        return val;
    }
}

循环链表

循环链表的最后一个节点指向第一个节点：

public class CircularLinkedList {
    private ListNode head;
    private ListNode tail;
    private int size;
    
    // 在头部插入
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        
        if (head == null) {
            head = tail = newNode;
            tail.next = head;  // 形成环
        } else {
            newNode.next = head;
            head = newNode;
            tail.next = head;  // 更新尾节点指向
        }
        size++;
    }
}

核心技巧：虚拟头节点 (Dummy Head)

在链表操作中，头节点的增删往往需要特殊处理（因为头节点没有前驱）。使用 哑节点/虚拟头节点 可以大幅简化代码：

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
// 所有的操作都对 current.next 进行，最后返回 dummy.next

数组 vs 链表 (详细对比)

操作	数组	链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)（预留空间）/ O(n)	O(1)（双链表）/ O(n)（单链表）
中间插入	O(n)	O(n)（查找）+ O(1)（插入）
头部删除	O(n)	O(1)
尾部删除	O(1)	O(1)（双链表）/ O(n)（单链表）
空间	连续，可能浪费	分散，额外指针开销

选择建议：

• 使用数组：

  • 需要频繁随机访问
  • 数据大小已知且固定
  • 需要缓存友好的性能

• 使用链表：

  • 需要频繁在头部插入删除
  • 数据大小不确定
  • 不需要随机访问

经典链表问题

1. 反转链表

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

// 递归法
public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

2. 检测环

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

3. 合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    // 处理剩余节点
    current.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

4. 删除倒数第 N 个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy;
    ListNode slow = dummy;
    
    // 快指针先走 n 步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // 快慢指针同时走
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 删除节点
    slow.next = slow.next.next;
    
    return dummy.next;
}

练习

1. 实现一个带头节点的单链表
2. LeetCode 206：反转链表
3. LeetCode 141：环形链表
4. LeetCode 21：合并两个有序链表
5. LeetCode 19：删除链表的倒数第 N 个节点
6. LeetCode 234：回文链表
7. LeetCode 160：相交链表