LeetCode链表问题全解析：从基础到进阶

安全风信子

发布于 2025-11-13 14:06:27

580

文章被收录于专栏：AI SPPECHAI SPPECH

一、链表基础与核心概念

1.1 链表的数据结构定义

链表是一种常见的线性数据结构，与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针连接起来的。链表中的每个元素称为节点（Node），每个节点包含两部分：数据域和指针域。

在LeetCode中，链表节点通常定义如下：

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

1.2 链表的优缺点

优点：

插入和删除操作效率高，不需要移动元素，只需修改指针，时间复杂度为O(1)
不需要预先分配固定大小的内存空间

缺点：

不能像数组那样进行随机访问，访问特定位置的元素需要从头开始遍历，时间复杂度为O(n)
每个节点需要额外的空间存储指针，内存开销较大

1.3 常见链表类型

单链表：每个节点只有一个指针，指向下一个节点
双链表：每个节点有两个指针，分别指向前驱节点和后继节点
循环链表：尾节点指向头节点，形成一个环

二、链表经典问题解析

2.1 反转链表（LeetCode 206）

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

解题思路

这道题是链表操作的基础题，有两种常见解法：迭代法和递归法。

方法一：迭代法

使用三个指针（prev、curr、nextTemp）来完成链表的反转。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next; // 暂存后继节点
        curr.next = prev;             // 反转当前节点的指针
        prev = curr;                  // prev指针前进
        curr = nextTemp;              // curr指针前进
    }
    return prev; // prev最终指向新的头节点
}

时间复杂度：O(n)，其中n是链表的长度。需要遍历链表一次。 空间复杂度：O(1)，只使用了常数级别的额外空间。

方法二：递归法

递归的核心思想是将问题分解为更小的子问题。对于反转链表，我们可以先反转剩余的链表，然后处理当前节点。

public ListNode reverseList(ListNode head) {
    // 递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    // 递归反转剩余链表
    ListNode newHead = reverseList(head.next);
    // 处理当前节点
    head.next.next = head;
    head.next = null;
    return newHead;
}

时间复杂度：O(n)，其中n是链表的长度。需要递归处理每个节点。 空间复杂度：O(n)，递归调用栈的深度为链表的长度。

2.2 环形链表（LeetCode 141）

题目描述：给定一个链表，判断链表中是否有环。

解题思路：使用快慢指针法（Floyd的龟兔算法）

慢指针每次移动一步
快指针每次移动两步
如果存在环，两个指针最终会相遇
如果链表有环，快指针永远不会指向null

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;        // 慢指针移动一步
        fast = fast.next.next;   // 快指针移动两步
    }
    return true;
}

时间复杂度：O(n)，其中n是链表中节点的数量。 空间复杂度：O(1)，只使用了两个指针。

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

题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例：输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

解题思路

使用双指针法，让第一个指针先走n+1步，然后两个指针一起走，当第一个指针到达链表末尾时，第二个指针正好指向要删除节点的前一个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 创建虚拟头节点，简化边界情况处理
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    
    // 第一个指针先走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;
}

时间复杂度：O(L)，其中L是链表的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

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

题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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

解题思路

使用递归或迭代的方法，每次比较两个链表的头节点，取较小的节点加入结果链表，然后继续处理剩余部分。

方法一：迭代法

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 创建虚拟头节点
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    
    // 比较两个链表的节点，取较小值加入结果链表
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    
    // 处理剩余节点
    curr.next = list1 != null ? list1 : list2;
    
    return dummy.next;
}

时间复杂度：O(n+m)，其中n和m分别是两个链表的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

方法二：递归法

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

时间复杂度：O(n+m)，其中n和m分别是两个链表的长度。 空间复杂度：O(n+m)，递归调用栈的深度为两个链表长度之和。

2.5 相交链表（LeetCode 160）

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

解题思路

使用双指针法，利用链表长度差的特性。

首先分别计算两个链表的长度
让较长的链表先走长度差步
然后两个链表一起走，第一个相同的节点就是相交节点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    
    // 计算两个链表的长度
    int lenA = getLength(headA);
    int lenB = getLength(headB);
    
    // 让较长的链表先走
    if (lenA > lenB) {
        headA = moveForward(headA, lenA - lenB);
    } else {
        headB = moveForward(headB, lenB - lenA);
    }
    
    // 一起走，找相交点
    while (headA != null && headB != null) {
        if (headA == headB) {
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
    
    return null;
}

// 计算链表长度
private int getLength(ListNode head) {
    int length = 0;
    while (head != null) {
        length++;
        head = head.next;
    }
    return length;
}

// 让链表前进k步
private ListNode moveForward(ListNode head, int k) {
    while (k > 0 && head != null) {
        head = head.next;
        k--;
    }
    return head;
}

时间复杂度：O(n+m)，其中n和m分别是两个链表的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

三、链表进阶问题

3.1 合并K个升序链表（LeetCode 23）

题目描述：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例：输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]

解题思路

这道题是合并两个有序链表的扩展，可以使用优先队列（小顶堆）来解决。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    
    // 创建小顶堆，根据节点值排序
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );
    
    // 将所有链表的头节点加入小顶堆
    for (ListNode head : lists) {
        if (head != null) {
            minHeap.offer(head);
        }
    }
    
    // 创建虚拟头节点
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    
    // 不断取出堆顶元素，并将下一个节点加入堆
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        curr.next = node;
        curr = curr.next;
        
        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }
    
    return dummy.next;
}

时间复杂度：O(N log K)，其中N是所有链表节点的总数，K是链表的数量。每次从堆中取出和插入元素的时间复杂度是O(log K)，总共进行N次这样的操作。 空间复杂度：O(K)，堆中最多存储K个节点。

3.2 排序链表（LeetCode 148）

题目描述：给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

解题思路

使用归并排序的思想：

找到链表的中点，将链表分成两部分
递归地对两部分进行排序
合并两个有序链表

public ListNode sortList(ListNode head) {
    // 递归终止条件：链表为空或只有一个节点
    if (head == null || head.next == null) {
        return head;
    }
    
    // 找到链表的中点，将链表分成两部分
    ListNode mid = findMiddle(head);
    ListNode rightHead = mid.next;
    mid.next = null; // 断开链表
    
    // 递归地对两部分进行排序
    ListNode left = sortList(head);
    ListNode right = sortList(rightHead);
    
    // 合并两个有序链表
    return mergeTwoLists(left, right);
}

// 使用快慢指针找到链表的中点
private ListNode findMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

// 合并两个有序链表
private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    curr.next = list1 != null ? list1 : list2;
    return dummy.next;
}

时间复杂度：O(n log n)，其中n是链表的长度。归并排序的时间复杂度为O(n log n)。 空间复杂度：O(log n)，递归调用栈的深度为log n。

3.3 两两交换链表中的节点（LeetCode 24）

题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：输入：head = [1,2,3,4] 输出：[2,1,4,3]

解题思路

可以使用递归或迭代的方法。这里介绍迭代法：

public ListNode swapPairs(ListNode head) {
    // 创建虚拟头节点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev = dummy;
    
    while (prev.next != null && prev.next.next != null) {
        // 保存要交换的两个节点
        ListNode first = prev.next;
        ListNode second = prev.next.next;
        
        // 进行交换
        first.next = second.next;
        second.next = first;
        prev.next = second;
        
        // 更新prev指针
        prev = first;
    }
    
    return dummy.next;
}

时间复杂度：O(n)，其中n是链表的长度。需要遍历链表一次。 空间复杂度：O(1)，只使用了常数级别的额外空间。

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

题目描述：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]

解题思路

这道题是两两交换链表节点的扩展，可以分解为以下步骤：

检查剩余的节点是否有k个，如果不足k个，则不进行翻转
翻转k个节点
递归处理剩余部分

public ListNode reverseKGroup(ListNode head, int k) {
    // 检查剩余的节点是否有k个
    ListNode curr = head;
    int count = 0;
    while (curr != null && count < k) {
        curr = curr.next;
        count++;
    }
    
    // 如果不足k个，不进行翻转
    if (count < k) {
        return head;
    }
    
    // 翻转k个节点
    ListNode prev = null;
    curr = head;
    for (int i = 0; i < k; i++) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    
    // 递归处理剩余部分
    head.next = reverseKGroup(curr, k);
    
    return prev;
}

时间复杂度：O(n)，其中n是链表的长度。需要遍历链表一次。 空间复杂度：O(n/k)，递归调用栈的深度为n/k。

四、链表实战技巧总结

4.1 常用技巧

虚拟头节点（Dummy Node）：处理头节点可能变化的情况，简化边界条件
快慢指针：解决链表环检测、找中点等问题
多指针法：用于链表反转等操作
递归：处理链表的合并、排序等问题
栈：用于逆序访问链表节点

4.2 常见陷阱与注意事项

空指针异常：操作节点前一定要检查节点是否为null
链表断开与连接：操作时要注意保持链表的完整性
边界条件处理：空链表、单节点链表等特殊情况
内存泄漏：在某些语言中，需要注意释放不需要的节点

4.3 性能优化建议

优先使用迭代而非递归，减少栈空间的使用
尽量一次遍历完成任务，避免多次遍历
对于频繁的查找操作，可以考虑使用哈希表等数据结构辅助

五、面试高频链表问题

5.1 环形链表 II（LeetCode 142）

题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

解题思路：结合快慢指针和数学推导

先使用快慢指针确定链表是否有环
如果有环，将一个指针重新指向链表头，然后两个指针同速前进，相遇点即为入环点

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    
    // 步骤1：使用快慢指针确定链表是否有环
    ListNode slow = head;
    ListNode fast = head;
    boolean hasCycle = false;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    
    // 如果没有环，返回null
    if (!hasCycle) {
        return null;
    }
    
    // 步骤2：找入环点
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;
}

时间复杂度：O(n)，其中n是链表的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

5.2 回文链表（LeetCode 234）

题目描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例：输入：head = [1,2,2,1] 输出：true

解题思路

使用快慢指针找到链表的中点
反转后半部分链表
比较前半部分和反转后的后半部分是否相同

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // 步骤1：找到链表的中点
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 步骤2：反转后半部分链表
    ListNode secondHalf = reverseList(slow.next);
    
    // 步骤3：比较前半部分和反转后的后半部分
    ListNode firstHalf = head;
    boolean isPalindrome = true;
    
    while (secondHalf != null) {
        if (firstHalf.val != secondHalf.val) {
            isPalindrome = false;
            break;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }
    
    // 恢复链表的结构（可选）
    slow.next = reverseList(secondHalf);
    
    return isPalindrome;
}

// 反转链表的辅助方法
private 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;
}

时间复杂度：O(n)，其中n是链表的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

5.3 复制带随机指针的链表（LeetCode 138）

题目描述：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 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;
    }
    
    // 第二次遍历，设置next和random指针
    curr = head;
    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);
}

时间复杂度：O(n)，其中n是链表的长度。 空间复杂度：O(n)，需要一个哈希表来存储原节点和新节点的对应关系。

六、链表思维训练与扩展

6.1 链表与其他数据结构的结合

链表+哈希表：解决随机指针复制、相交链表等问题
链表+优先队列：解决合并K个有序链表等问题
链表+栈：解决回文链表、逆序输出等问题

6.2 链表在实际应用中的体现

操作系统中的内存管理：使用链表来管理空闲内存块
浏览器的前进后退功能：使用双向链表实现
LRU缓存：使用双向链表和哈希表结合实现
编辑器的撤销功能：使用链表记录操作历史

6.3 链表问题的变形与扩展

双向链表的实现与操作
循环链表的应用
链表的分割与合并
链表的排序算法实现

七、总结与展望

链表作为一种基础的数据结构，在算法面试中占据重要地位。通过本文的学习，我们不仅掌握了链表的基础知识和常见操作，还深入解析了LeetCode上的经典链表问题，包括基础的反转链表、环形链表检测，以及进阶的合并K个有序链表、K个一组翻转链表等。

在解决链表问题时，我们需要注意以下几点：

掌握基础操作：如遍历、插入、删除等
熟悉常用技巧：如虚拟头节点、快慢指针、多指针法等
注意边界条件：空链表、单节点链表等特殊情况
理解算法思想：递归、分治、贪心等思想在链表问题中的应用

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除

链表

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度