Java算法题-复制带随机指针的链表问题

问题

给定一个链表，每个节点包含一个额外的随机指针，该指针可以指向链表中的任何节点，也可以为 null。请返回这个链表的深度拷贝。

引言

在这个算法问题中，我们将探讨一个与复制带随机指针的链表相关的挑战。与普通链表不同，这个链表的每个节点都包含一个额外的随机指针，可以指向链表中的任何节点，也可以为 null。

算法思路

为了复制带随机指针的链表，我们需要在原链表的节点和复制链表的节点之间建立映射关系。我们可以使用HashMap来存储这种映射关系。

具体思路如下：

1. 第一次遍历原链表，将原节点和新节点的对应关系存储在HashMap中。
2. 第二次遍历原链表，根据HashMap中的映射关系，为每个新节点设置正确的next指针和random指针。
3. 返回新链表的头节点。

代码实现

以下是使用Java实现的解决方案：

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

    public Node() {}

    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 curr = head;

        // 第一次遍历，建立映射关系
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }

        curr = head;

        // 第二次遍历，设置新节点的next和random指针
        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 是链表的长度。
• 空间复杂度：使用了额外的HashMap来存储映射关系，空间复杂度为 O(N)。

示例和测试

你可以使用以下代码来测试算法：

public class Main {
    public static void main(String[] args) {
        CopyRandomList solution = new CopyRandomList();

        // 创建一个示例链表
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node1.next = node2;
        node1.random = node2;
        node2.random = node2;

        Node copiedList = solution.copyRandomList(node1);

        // 打印新链表的值和随机指针值
        while (copiedList != null) {
            System.out.print("Value: " + copiedList.val);
            if (copiedList.random != null) {
                System.out.println(", Random: " + copiedList.random.val);
            } else {
                System.out.println(", Random: null");
            }
            copiedList = copiedList.next;
        }
    }
}

总结

复制带随机指针的链表问题是一个典型的HashMap应用问题。通过建立原链表节点和新链表节点的映射关系，我们能够高效地解决这个问题。熟练运用HashMap可以帮助我们解决更多类似的问题。