链表常见算法实现

#算法 #java

链表题的几个核心套路：哨兵节点、快慢指针、双指针、三指针反转。

1. 合并两个有序链表

输入：l1 = [1,2,4]，l2 = [1,3,4]
输出：[1,1,2,3,4,4]

迭代写法，用哨兵节点省掉对第一个节点的特殊判断：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = (l1 == null) ? l2 : l1;
    return dummy.next;
}

递归写法更简洁：

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

2. 链表反转

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 成为新头节点
}

2.1 每 K 个节点反转

public ListNode reverseKGroup(ListNode head, int k) {
    // 先检查剩余节点够不够 k 个
    ListNode check = head;
    for (int i = 0; i < k; i++) {
        if (check == null) return head;
        check = check.next;
    }

    // 反转前 k 个
    ListNode prev = null, curr = head;
    for (int i = 0; i < k; i++) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    // 递归处理剩余部分
    head.next = reverseKGroup(curr, k);
    return prev;
}

3. 查找中间节点

快指针每次走两步，慢指针走一步，快指针到头时慢指针正好在中间：

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

偶数长度链表返回第二个中间节点（比如 [1,2,3,4] 返回 3）。

4. 判断是否有环

快慢指针，有环必然相遇：

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

5. 删除倒数第 N 个节点

双指针保持 N 的间距，first 到末尾时 second 正好在目标节点的前一个：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode first = dummy, second = dummy;

    // first 先走 n+1 步
    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;
}

哨兵节点的作用：删除头节点时不需要特殊处理。