力扣经典150题第五十九题：随机链表的复制

用户8589624

发布于 2025-11-13 16:16:11

670

文章被收录于专栏：nginxnginx

标题：使用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();
    }
}