【LeetCodehot100】 T138 随机链表的复制 T148：排序链表

y = xⁿ

536人浏览 · 2026-03-16 20:39:11

y = xⁿ · 2026-03-16 20:39:11 发布

T138 随机链表的复制

这道题刚开始看很难理解，我们可以先看答案，跟着实例理解题目在干什么然后来分析这道题的小巧思
题目理解：
这道题和常见的链表不同
常见链表：

1 → 2 → 3 → 4 → 5

每个节点只有一个指针：next

这道题多了一个指针

class Node {
    int val;
    Node next;
    Node random;
}

也就是说 每个节点有两个指针：

指针	作用
next	指向下一个节点
random	可以指向链表中任意节点

random 可以随便指

举个例子：

假设链表是：

1 → 2 → 3

next关系：

1.next = 2
2.next = 3
3.next = null

random关系可能是：

1.random → 3
2.random → 1
3.random → 2

题目要干什么

复制一份一模一样的链表

这包含了两个重要信息

一模一样
复制后的链表结构要一样：

next关系一样
random关系一样

深拷贝

复制出来的节点必须是：

新的节点

而不是原来的节点。

例如：

原链表：

A → B → C

复制后：

A’ → B’ → C’

并且：

A’.random 指向 C’
B’.random 指向 A’

而不是：

A’.random 指向 C ❌

题目的本质
想成为本质高手，就理解一句话：

复制一个带 random 指针的链表

核心思想（HashMap映射）

建立映射关系：

旧节点 → 新节点

例如：

1 → 1’
2 → 2’
3 → 3’

存储在：

HashMap<Node, Node>

整体流程

算法分 两次遍历：

第一遍：创建所有新节点
第二遍：连接 next 和 random
流程图：

在这里插入图片描述

代码实现

if(head==null)return null;
Map<Node,Node> map=new HashMap<>;
Node cur=head;

//第一步：复制所有节点
while(cur!=null){
map.put(cur,new Node(cur.val))
cur=cur.next;
}

//第二步：连接next和random
while(cur!=null){
Node newNode=map.get(cur);
newNode.next=map.get(cur.next);
newNode.random=map.get(cur.random);

cur=cur.next;
}
return map.get(head);

题目小坑

在最后return阶段

return map.get(head);;

而不是：

return head;

题目要求返回复制后的链表，即为：return map.get(head);

本题感悟

理解了Hash Map的映射关系

map.put(cur,new Node(cur.val)) // 创建了（1，1‘）

实现两个节点连接的方式

newNode.next=map.get(cur.next); // next和next的连接
newNode.random=map.get(cur.random); // random和random的连接

T148：排序链表

题目要求:

给你一个链表，把链表排序。

题目要求很简单，但是这题难在找到正确的算法结构，否则很容易超时

题目真正的限制

时间复杂度：O(n log n)
空间复杂度：O(1)（尽量）

所以不能用：

数组排序
Collections.sort

因为：链表随机访问慢

寻找算法

排序	适不适合链表
快速排序	不太适合
归并排序	非常适合

归并才是最终选择

链表不支持随机访问
但非常适合拆分和合并

归并排序的理解

归并有三个步骤：

1 拆分链表
2 递归排序
3 合并两个有序链表

例如：

4 → 2 → 1 → 3

拆成：

4 → 2
1 → 3

再拆：

4 2 1 3

然后开始合并：

4 和 2 → 2 → 4
1 和 3 → 1 → 3

最后：

2 → 4
1 → 3

合并：

1 → 2 → 3 → 4

如何拆成两半？
核心技巧：

快慢指针

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

最终：

slow 在中点

然后断开链表：

ListNode mid = slow.next;
slow.next = null;

代码实现

public ListNode sortList(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;
    }

    ListNode mid = slow.next;
    slow.next = null;

    // 递归排序
    ListNode left = sortList(head);
    ListNode right = sortList(mid);

    // 合并
    return merge(left, right);
}
//把两个有序链表合并成一个有序链表
private ListNode merge(ListNode l1, ListNode l2){
    ListNode dummy = new ListNode(0);
    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;
    }

    if(l1 != null) cur.next = l1;
    if(l2 != null) cur.next = l2;

    return dummy.next;
}