标题：使用Java实现随机链表的深拷贝
随机链表的深拷贝是一道经典的链表问题，需要在复制链表的同时处理随机指针。在本文中，我们将使用Java来解决LeetCode上的第五十九题，实现随机链表的深拷贝。
1. 题目分析
题目要求给定一个随机链表的头节点，我们需要复制该链表并返回复制链表的头节点。每个节点除了有普通的next指针外，还有一个random指针，指向链表中的任意节点或空节点。
2. 解题思路
为了实现随机链表的深拷贝，我们可以使用HashMap来存储原节点和复制节点之间的映射关系。具体步骤如下：
- 第一次遍历：创建新节点，并将原节点和新节点的映射关系存储在HashMap中。
- 第二次遍历：根据HashMap中的映射关系，复制原链表的next指针和random指针。
3. Java代码实现
import java.util.HashMap; import java.util.Map; class Node { int val; Node next, random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } public class CopyRandomList { public Node copyRandomList(Node head) { 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; } cur = head; // 第二次遍历：复制next指针和random指针 while (cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } return map.get(head); } }
4. 测试示例
我们使用几个示例来测试我们的代码：
public class Main { public static void main(String[] args) { // 示例1 Node node1 = new Node(7); Node node2 = new Node(13); Node node3 = new Node(11); Node node4 = new Node(10); Node node5 = new Node(1); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node2.random = node1; node3.random = node5; node4.random = node3; node5.random = node1; CopyRandomList solution = new CopyRandomList(); Node copiedList1 = solution.copyRandomList(node1); printList(copiedList1); // 示例2 Node node6 = new Node(1); Node node7 = new Node(2); node6.next = node7; node6.random = node7; node7.random = node7; Node copiedList2 = solution.copyRandomList(node6); printList(copiedList2); } public static void printList(Node head) { Node cur = head; while (cur != null) { System.out.print("[" + cur.val + ", "); if (cur.random != null) { System.out.print(cur.random.val); } else { System.out.print("null"); } System.out.print("] "); cur = cur.next; } System.out.println(); } }
5. 总结
本文介绍了如何使用Java实现随机链表的深拷贝。通过HashMap来建立原节点和新节点之间的映射关系，实现了链表的深拷贝。这是一道经典的链表问题，在面试中也经常会被考察到。
public class BlogEnding { public static void main(String[] args) { encourageEngagement(); } public static void encourageEngagement() { System.out.println("🚀 感谢您阅读本文！如果您觉得有收获，请一键三连：点赞 ❤️️、转发 🔁、评论 💬，并加关注哦！"); } }
