链表核心算法题解汇总 | 极客日志

Javajava算法

链表核心算法题解汇总

本文总结了链表的核心算法技巧与常见 LeetCode 题解。内容包括链表常用操作（画图、虚拟头结点、快慢指针）、两数相加、两两交换节点（迭代与递归）、重排链表、合并 K 个升序链表（堆、分治、暴力）以及 K 个一组翻转链表。所有代码示例均基于 Java 语言实现，涵盖了解题思路分析与完整代码逻辑。

暗影行者发布于 2026/3/30更新于 2026/4/131 浏览

链表核心算法题解汇总

一、链表常用技巧与操作总结

技巧：

画图解题。
使用虚拟头结点。
像有插入类似操作时，直接定义变量，不用考虑节点丢失情况。
快慢指针。

操作：

创建新节点。
尾插。
头插。

二、2.两数相加

题目：2.两数相加

题目描述：给你两个链表，每个链表都表示一个逆位的数，将两个数相加。相加后的结果不会出现链表最后节点为 0 的情况。

解题思路：

模拟两个数字相加即可。
遍历两个链表，对应节点值相加，放在一个变量 sum 中，结果链表就接上 sum%10 的节点，sum / 10 表示进位的数。

解题代码：

// 时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode(0); // 虚拟头结点
        ListNode pre = newHead;
        int sum = 0;
        while (l1 != null || l2 != null || sum != 0) {
            if (l1 != null) { sum += l1.val; l1 = l1.next; }
            if (l2 != null) { sum += l2.val; l2 = l2.next; }
            pre.next = new ListNode(sum % 10);
            pre = pre.next;
            sum /= 10;
        }
        return newHead.next;
    }
}

三、24.两两交换链表中的节点

题目：24.两两交换链表中的节点

题目解析：

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

// 时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode pre = newHead;
        ListNode cur1 = pre.next;
        ListNode cur2 = cur1.next;
        ListNode last = cur2.next;
        while (cur1 != null && cur2 != null) {
            // 交换
            pre.next = cur2;
            cur2.next = cur1;
            cur1.next = last;
            // 向后移动
            pre = cur1;
            if (pre.next == null) break;
            cur1 = pre.next;
            if (cur1.next == null) break;
            cur2 = cur1.next;
            last = cur2.next;
        }
        return newHead.next;
    }
}

// 时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = head.next;
        head.next = newHead.next;
        newHead.next = head;
        head.next = swapPairs(head.next);
        return newHead;
    }
}

// 时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
    public void reorderList(ListNode head) {
        if (head.next == null || head.next.next == null) return;
        // 快慢双指针 找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 头插法 逆置
        ListNode head2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }
        head2 = head2.next;
        // 合并两个链表
        ListNode newHead = new ListNode(0);
        ListNode pre = newHead;
        while (head != null) {
            if (head != null) {
                pre.next = head;
                head = head.next;
                pre = pre.next;
            }
            if (head2 != null) {
                pre.next = head2;
                head2 = head2.next;
                pre = pre.next;
            }
        }
        head = newHead.next;
    }
}

// 时间复杂度：O(N*K*logK) 空间复杂度：O(k)
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        ListNode ret = new ListNode(0);
        ListNode pre = ret;
        for (ListNode head : lists) {
            if (head != null) heap.offer(head);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = pre.next;
            cur = cur.next;
            if (cur != null) heap.offer(cur);
        }
        return ret.next;
    }
}

// 时间复杂度：O(N*K*logK) 空间复杂度：O(k)
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return mrege(0, lists.length - 1, lists);
    }

    public ListNode mrege(int left, int right, ListNode[] lists) {
        if (left > right) return null;
        if (left == right) return lists[left];
        // 分：分成两个区间
        int mid = (left + right) / 2;
        ListNode head1 = mrege(left, mid, lists);
        ListNode head2 = mrege(mid + 1, right, lists);
        // 合并两个有序链表
        return add(head1, head2);
    }

    public ListNode add(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode newHead = new ListNode(0);
        ListNode pre = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                pre = pre.next;
                l1 = l1.next;
            } else {
                pre.next = l2;
                pre = pre.next;
                l2 = l2.next;
            }
        }
        if (l1 != null) pre.next = l1;
        if (l2 != null) pre.next = l2;
        return newHead.next;
    }
}

// 时间复杂度：O(N*K*K) 空间复杂度：O(1)
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        ListNode ret = lists[0];
        for (int i = 1; i < lists.length; i++) {
            ret = add(ret, lists[i]);
        }
        return ret;
    }

    public ListNode add(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode newHead = new ListNode(0);
        ListNode pre = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                pre = pre.next;
                l1 = l1.next;
            } else {
                pre.next = l2;
                pre = pre.next;
                l2 = l2.next;
            }
        }
        if (l1 != null) pre.next = l1;
        if (l2 != null) pre.next = l2;
        return newHead.next;
    }
}

// 时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        n /= k;
        cur = head;
        ListNode ret = new ListNode(0);
        ListNode pre = ret;
        for (int i = 0; i < n; i++) {
            ListNode tmp = cur;
            for (int j = 0; j < k; j++) {
                ListNode next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
                cur = next;
            }
            pre = tmp;
        }
        pre.next = cur;
        return ret.next;
    }
}