链表面试必刷双题解 | 随机链表复制 + 排序链表 高频真题全解析

目录

138. 随机链表的复制

题目链接

题目简介

解题思路

满分代码（极简注释版）

148. 排序链表

题目链接

题目简介

解题思路

满分代码（规范命名 + 超强注释）

138. 随机链表的复制

题目链接

138. 随机链表的复制 - 力扣（LeetCode）

题目简介

给你一个长度为n的随机链表，每个节点包含一个额外的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。

解题思路

普通链表复制只需处理next指针，而本题难点在于随机指针random的指向无法一次性确定。我们用哈希表完美解决，核心分两步遍历，逻辑简单无坑：

1. 第一遍遍历：不处理指针关系，仅克隆所有节点，用HashMap存储原节点 → 新节点的映射关系；
2. 第二遍遍历：根据哈希表，直接为新节点赋值next和random指针，一步到位。

满分代码（极简注释版）

java

运行

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { // 边界判断：空链表直接返回 if(head == null){ return null; } // 哈希表：key = 原节点，value = 克隆的新节点 Map<Node,Node> map = new HashMap<>(); Node cur = head; // 第一步：遍历链表，克隆所有节点，建立映射关系 while(cur != null){ map.put(cur, new Node(cur.val)); cur = cur.next; } // 第二步：再次遍历，为新节点设置 next 和 random 指针 cur = head; while(cur != null){ // 复制 next 指针 if(cur.next != null){ map.get(cur).next = map.get(cur.next); } // 复制 random 指针 if(cur.random != null){ map.get(cur).random = map.get(cur.random); } cur = cur.next; } // 返回克隆链表的头节点 return map.get(head); } }

148. 排序链表

题目链接

148. 排序链表 - 力扣（LeetCode）

题目简介

给你链表的头结点head，请将其按升序排列并返回排序后的链表，要求时间复杂度 O(nlogn)。

解题思路

链表排序最优解：归并排序（递归版）链表不支持随机访问，快排 / 堆排都不适用，而归并排序天然适配链表结构，核心分两大步骤：

1. 分割链表：快慢指针找中点，将链表从中间切断，递归分割至每个子链表只有 1 个节点（天然有序）；
2. 合并有序链表：双指针合并两个有序子链表，最终得到完整有序链表。

满分代码（规范命名 + 超强注释）

java

运行

/** * Definition for singly-linked list. * 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; } * } */ class Solution { public ListNode sortList(ListNode head) { // 递归终止条件：空节点 或 单个节点，无需排序 if(head == null || head.next == null){ return head; } // 快慢指针：寻找链表中点（偶数节点找左中点） ListNode fast = head, slow = head; while(fast.next != null && fast.next.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(Integer.MIN_VALUE); ListNode cur = dummy; while(left != null && right != null){ if(left.val < right.val){ cur.next = left; left = left.next; }else{ cur.next = right; right = right.next; } cur = cur.next; } // 拼接剩余未遍历完的节点 cur.next = left != null ? left : right; // 返回排序后的链表头 return dummy.next; } }