目录

一、链表基础原理

链表的分类

链表的特性

二、核心解题方法

1. 双指针法

2. 递归法

3. 哈希表法

4. 哑节点（虚拟头节点）

三、经典题型分类与代码实现

（一）基础操作类

1. 反转链表（LeetCode 206）

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

3. 删除链表的倒数第 N 个节点（LeetCode 19）

（二）环与相交类

1. 环形链表（LeetCode 141）

2. 环形链表 II（LeetCode 142）

3. 相交链表（LeetCode 160）

（三）回文与对称类

回文链表（LeetCode 234）

（四）排序与复杂重组类

1. 排序链表（LeetCode 148）

2. K 个一组翻转链表（LeetCode 25）

3. 随机链表的复制（LeetCode 138）

（五）数值计算类

两数相加（LeetCode 2）

（六）困难拓展类：合并 K 个升序链表（LeetCode 23）

总结

---

一、链表基础原理

链表是一种线性数据结构，由 ** 节点（Node）** 组成，每个节点包含两部分：

• 数据域：存储节点的值（如 int val）。
• 指针域：存储下一个节点的引用（如 ListNode next）。

链表的分类

• 单链表：每个节点只有一个指向下一节点的指针，尾节点指向 null。
• 双链表：每个节点有两个指针（prev 指向前一节点，next 指向后一节点）。
• 循环链表：尾节点指向头节点，形成 “环”。

链表的特性

• 插入 / 删除高效：已知位置时，时间复杂度为 O(1)（仅需修改指针）。
• 访问低效：访问第 k 个节点需遍历，时间复杂度 O(n)。

二、核心解题方法

1. 双指针法

• 快慢指针：快指针速度是慢指针的 2 倍（或其他倍数），用于：
  • 找链表中点（如回文链表、排序链表的归并）。
  • 判断环形链表（相遇则有环）。
  • 找环形链表的入环点（相遇后，一个指针回 head，同速移动）。
• 前后指针：两个指针一前一后，用于：
  • 反转链表（prev 和 curr 配合修改指针方向）。
  • 删除倒数第 N 个节点（快指针先走 N 步，再一起走）。

2. 递归法

递归的本质是将大问题拆解为相同逻辑的子问题，适用于：

• 反转链表（反转剩余部分，再连接当前节点）。
• 合并有序链表（比较头节点，递归合并剩余部分）。

3. 哈希表法

用于记录节点的 “访问状态” 或 “映射关系”，适用于：

• 判断环形链表（记录已访问节点，重复则有环）。
• 相交链表（记录 A 链表节点，遍历 B 时判断是否存在）。
• 随机链表的复制（记录原节点到新节点的映射，处理 random 指针）。

4. 哑节点（虚拟头节点）

当链表的头节点操作需要特殊处理时（如合并链表时头节点不确定、删除头节点），创建一个 val 无意义的节点作为头节点的前驱，简化逻辑。通常是dummy～

三、经典题型分类与代码实现

（一）基础操作类

1. 反转链表（LeetCode 206）

问题：反转单链表（如 1->2->3->null → 3->2->1->null）。

方法：双指针或递归。

注：此处的null也可以是其他节点；用于反转部分节点

// 双指针法
public ListNode reverseList(ListNode head) {
    // prev通常是链表尾的指向
    ListNode prev = null;
    // 当前节点，后面逐渐后移，至null
    ListNode curr = head;
    while (curr != null) {
        //保存当前节点的下一个节点，避免后续当前节点的移动
        ListNode nextTemp = curr.next;
        //将当前指向prev表尾
        curr.next = prev;
        // prev指针左移/前移
        prev = curr;
        //当前指针后移，进行下一轮交换
        curr = nextTemp;
    }
    //最终prev从最右端移到了最左端，成为了头节点
    return prev;
}


// 递归法
public ListNode reverseList(ListNode head) {

    // 递归终止条件
    if (head == null || head.next == null) return head;
    //1->2->3->4->null
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}
 /**
递归处理 “剩余部分”

ListNode newHead = reverseList(head.next);
以链表 1->2->3->4->null 为例，递归调用会不断深入：
第一次调用：head=1，处理 head.next=2 → 进入下一层递归。
第二次调用：head=2，处理 head.next=3 → 进入下一层递归。
第三次调用：head=3，处理 head.next=4 → 进入下一层递归。
第四次调用：head=4，满足 head.next == null → 触发终止条件，返回 4（此时 newHead=4）。
步骤 3：调整 “当前节点” 与 “后继” 的指针

head.next.next = head;
head.next = null;
回到第三次调用（head=3，newHead=4）：
head.next 是 4，所以 head.next.next = head → 等价于 4.next = 3，此时链表变为 3<->4。
head.next = null → 断开 3->4 的旧连接，最终 3 的 next 为 null，链表变为 4->3->null。
返回 newHead=4 → 回到第二次调用。
回到第二次调用（head=2，newHead=4）：
head.next 是 3，所以 3.next = 2 → 链表变为 4->3->2。
head.next = null → 断开 2->3 的旧连接，2 的 next 为 null，链表变为 4->3->2->null。
返回 newHead=4 → 回到第一次调用。
回到第一次调用（head=1，newHead=4）：
head.next 是 2，所以 2.next = 1 → 链表变为 4->3->2->1。
head.next = null → 断开 1->2 的旧连接，1 的 next 为 null，链表变为 4->3->2->1->null。
返回 newHead=4 → 最终整个链表完成反转。
    **/

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

问题：将两个升序链表合并为一个升序链表。

方法：双指针 + 哑节点。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 设置哑节点，因为两个头节点都要被处理
    ListNode dummy = new ListNode(0);
    // 设置当前节点，后续不断后移
    ListNode prev = dummy;
    // 当两个链表都不为空时继续合并
    while (list1 != null && list2 != null) {
        // 将值更小的节点优先加入，同时移动结果链表和当前链表
        if (list1.val <= list2.val) {
            // 实现连接
            prev.next = list1;
            list1 = list1.next;
        } else {
            prev.next = list2;
            list2 = list2.next;
        }
        prev = prev.next;
    }
    // 哪个表空了就直接连上，注意是在循环结束后
    prev.next = list1 != null ? list1 : list2;
    // 返回哑节点的next，刚好是头节点
    return dummy.next;
}

3. 删除链表的倒数第 N 个节点（LeetCode 19）

问题：删除链表的倒数第 n 个节点（如 1->2->3->4->5，n=2 → 1->2->3->5）。

方法：快慢指针 + 哑节点（快指针先走 n 步，再一起走，找到待删除节点的前驱）。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 哑节点构造的简化写法，和 “先 new 哑节点再设置dummy.next = head” 效果完全一致
    // ListNode dummy = new ListNode(0); dummy.next = head;
    ListNode dummy = new ListNode(0, head);
    // 初始化，都先在哑节点启动
    ListNode fast = dummy, slow = dummy;
    // 快节点先走n+1步（此处如果是i<n就说多走n步，while循环条件需要改为fast.next!=null）
    for (int i = 0; i <= n; i++) fast = fast.next;
    while (fast != null) {
        // 两个指针同时移动，最终fast到达null，slow比fast落后n+1个位置，在需要删除的节点前驱
        fast = fast.next;
        slow = slow.next;
    }
    // 此处对第n个节点进行删除
    slow.next = slow.next.next;
    //返回头节点
    return dummy.next;
}

（二）环与相交类

1. 环形链表（LeetCode 141）

问题：判断链表是否有环。

方法：快慢指针（快指针走 2 步，慢指针走 1 步，相遇则有环）。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;
    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;
}

注：哈希表法也可以解决

    public ListNode removeNthFromEnd(ListNode head, int n) {
         if (head == null) {
             return null;
         }
        
         // 第一步：遍历链表，用Map记录每个节点的索引和节点本身
         Map<Integer, ListNode> indexToNode = new HashMap<>();
         ListNode current = head;
         int length = 0; // 链表总长度
        
         while (current != null) {
             indexToNode.put(length, current); // 索引从0开始
             current = current.next;
             length++;
         }
        
         // 第二步：计算要删除的节点的索引（倒数第n个 = 正数第 length - n 个）
         int deleteIndex = length - n;
        
         // 特殊情况：删除的是头节点（索引0）
         if (deleteIndex == 0) {
             return head.next;
         }
        
         // 第三步：找到目标节点的前一个节点，删除目标节点
         ListNode prevNode = indexToNode.get(deleteIndex - 1); // 前一个节点的索引
         prevNode.next = prevNode.next.next; // 跳过目标节点
        
         return head;

2. 环形链表 II（LeetCode 142）

问题：返回环形链表的入环第一个节点。

方法：快慢指针相遇后，一个指针回 head，同速移动，相遇处为入环点。

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) return null;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) { // 相遇，存在环
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr; // 入环点
        }
    }
    return null;
}

3. 相交链表（LeetCode 160）

问题：找到两个单链表相交的起始节点（不相交返回 null）。

方法：双指针（A 走完走 B，B 走完走 A，相遇则相交）。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

（三）回文与对称类

回文链表（LeetCode 234）

问题：判断链表是否为回文（如 1->2->2->1 是回文，1->2 不是）。

方法：找中点 + 反转后半段 + 比较。

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    // 找中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 反转后半段
    ListNode reversedHalf = reverseList(slow.next);
    // 比较前半段和反转后的后半段
    ListNode p1 = head, p2 = reversedHalf;
    while (p2 != null) {
        if (p1.val != p2.val) return false;
        p1 = p1.next;
        p2 = p2.next;
    }
    return true;
}

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

（四）排序与复杂重组类

1. 排序链表（LeetCode 148）

问题：对链表进行升序排序。

方法：归并排序（找中点 + 递归合并）。

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 找中点
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null; // 拆分链表
    // 递归排序左右两部分
    ListNode left = sortList(head);
    ListNode right = sortList(mid);
    // 合并
    ListNode dummy = new ListNode(0);
    ListNode prev = dummy;
    while (left != null && right != null) {
        if (left.val <= right.val) {
            prev.next = left;
            left = left.next;
        } else {
            prev.next = right;
            right = right.next;
        }
        prev = prev.next;
    }
    prev.next = left != null ? left : right;
    return dummy.next;
}

2. K 个一组翻转链表（LeetCode 25）

问题：每 k 个节点一组进行翻转（如 1->2->3->4->5，k=2 → 2->1->4->3->5）。

方法：分组处理，每组内部反转，再拼接。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    while (true) {
        // 检查剩余节点是否足够k个
        ListNode tail = prev;
        for (int i = 0; i < k; i++) {
            tail = tail.next;
            if (tail == null) return dummy.next;
        }
        ListNode nextGroup = tail.next;
        // 反转当前k个节点
        ListNode[] reversed = reverse(prev.next, tail);
        ListNode newHead = reversed[0], newTail = reversed[1];
        // 拼接
        prev.next = newHead;
        newTail.next = nextGroup;
        prev = newTail;
    }
}

// 反转从head到tail的链表，返回新的头和尾
private ListNode[] reverse(ListNode head, ListNode tail) {
    ListNode prev = tail.next, curr = head;
    while (prev != tail) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return new ListNode[]{tail, head};
}

3. 随机链表的复制（LeetCode 138）

问题：复制一个带有 random 指针的链表（random 可能指向任意节点或 null）。

方法：哈希表记录原节点到新节点的映射，先复制 next 指针，再处理 random 指针。

public Node copyRandomList(Node head) {
    if (head == null) return null;
    Map<Node, Node> map = new HashMap<>();
    Node curr = head;
    // 复制节点，存储映射
    while (curr != null) {
        map.put(curr, new Node(curr.val));
        curr = curr.next;
    }
    curr = head;
    // 处理next和random指针
    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);
}

（五）数值计算类

两数相加（LeetCode 2）

问题：两个非空链表表示两个非负整数（每位数字逆序存储），求它们的和。

方法：模拟加法，注意进位，哑节点存储结果。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
    }
    return dummy.next;
}

（六）困难拓展类：合并 K 个升序链表（LeetCode 23）

问题：合并 k 个升序链表，返回合并后的升序链表。

方法：优先队列（最小堆）或分治合并。

// 方法1：优先队列（最小堆）
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode list : lists) {
        if (list != null) pq.offer(list);
    }
    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;
}

// 方法2：分治合并
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);
}

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

总结

链表题的核心在于指针的灵活操作。需掌握 “双指针、递归、哈希表、哑节点” 这四类方法，将大部分题型拆解为 “模板化” 的逻辑。

• 环和相交问题：快慢指针的 “相遇逻辑”。
• 反转和合并：双指针 + 哑节点的 “拼接模板”。
• 复杂重组（如 K 个一组、排序）：将问题拆分为 “子问题”（递归或分组），再逐一解决。

---