复制带随机指针的链表

[PisecesPeng]

回文链表

给你一个长度为n的链表, 每个节点包含一个额外增加的随机指针random, 该指针可以指向链表中的任何节点或空节点.

构造这个链表的深拷贝.
深拷贝应该正好由n个全新节点组成, 其中每个新节点的值都设为其对应的原节点的值.
新节点的next指针和random指针也都应指向复制链表中的新节点,
并使原链表和复制链表中的这些指针能够表示相同的链表状态.
复制链表中的指针都不应指向原链表中的节点.

例如, 如果原链表中有x和y两个节点, 其中x.random --> y.
那么在复制链表中对应的两个节点x和y, 同样有x.random --> y.

返回复制链表的头节点.

用一个由n个节点组成的链表来表示输入/输出中的链表.
每个节点用一个[val, random_index]表示:

• val: 一个表示 Node.val 的整数.
• random_index: 随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点, 则为null.

你的代码只接受原链表的头节点head作为传入参数.

示例 1:

输入: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出: [[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

输入: head = [[1,1],[2,1]]
输出: [[1,1],[2,1]]

示例 3:

输入: head = [[3,null],[3,0],[3,null]]
输出: [[3,null],[3,0],[3,null]]

示例 4:

输入: head = []
输出: []
解释: 给定的链表为空(空指针), 因此返回null.  

提示:

• 0 <= n <= 1000.
• -10000 <= Node.val <= 10000.
• Node.random 为空(null)或指向链表中的节点.

题目地址: https://leetcode-cn.com/problems/copy-list-with-random-pointer/

[PisecesPeng]

LeetCode题解

解题思路

• 递归 + 哈希表

代码

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

Map<Node, Node> cachedNode = new HashMap<Node, Node>();

public Node func(Node head) {
    if (head == null) {
        return null;
    }
    if (!cachedNode.containsKey(head)) {
        Node headNew = new Node(head.val);
        cachedNode.put(head, headNew);
        headNew.next = func(head.next);
        headNew.random = func(head.random);
    }
    return cachedNode.get(head);
}

[PisecesPeng]

LeetCode题解

解题思路

• 迭代,
• 将现有结点间再重新构造一套相同的结点, 再将随机结点关系在新结点基础上构造, 最后脱离原链表.

代码

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public Node func(Node head) {
    if (head == null) {
        return null;
    }
    // 1. 在现有结点间构造相同结点
    for (Node node = head; node != null; node = node.next.next) {
        Node nodeNew = new Node(node.val);
        nodeNew.next = node.next;
        node.next = nodeNew;
    }
    // 2. 将随机结点关系在新结点上构造
    for (Node node = head; node != null; node = node.next.next) {
        Node nodeNew = node.next;
        nodeNew.random = (node.random != null) ? node.random.next : null;
    }
    // 3. 脱离原链表
    Node headNew = head.next;
    for (Node node = head; node != null; node = node.next) {
        Node nodeNew = node.next;
        node.next = node.next.next;
        nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
    }
    return headNew;
}