35.复杂链表的复制

难点在于，random结点可能还没出创建
我们可以使用一个map存储结点的创建情况
使用递归的思想

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

    public Node copyRandomList(Node head) {
		// base case
        if (head == null) {
            return null;
        }
		// map中不存在该结点，需要创建，同时会把该结点的下一个结点和random结点都创建
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
		// 存在时直接返回
        return cachedNode.get(head);
    }
}

另外一种思路（节省）
将新旧结点串成串，如A→A′→B→B′→C→C′
我们可以直接找到每一个拷贝节点 S'的随机指针应当指向的节点，即为其原节点 S 的随机指针指向的节点 T 的后继节点 T'。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况
然后再重新拆分链表

// class Solution {
//     Map<Node,Node> map = new HashMap<Node,Node>();
//     public Node copyRandomList(Node head) {
//         if(head == null)return null;
//         if(!map.containsKey(head)){
//             Node newhead = new Node(head.val);
//             map.put(head,newhead);
//             newhead.next = copyRandomList(head.next);
//             newhead.random = copyRandomList(head.random);
//         }
//         return map.get(head);
//     }
// }
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        for(Node node = head; node !=null;node = node.next.next){
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        for(Node node = head; node != null;node = node.next.next){
            Node newNode = node.next;
            newNode.random = (node.random != null) ? node.random.next : null;
        }
        // 记录新链表的头结点
        Node newHead = head.next;
        for(Node node = head; node !=null;node = node.next){
            Node newNode = node.next;
            // 需要改变原链表结点的next指向，使用for循环定义中，不能使用node = node.next.next
            node.next = node.next.next;
            newNode.next = (newNode.next != null) ? newNode.next.next : null;
        }
        return newHead;
    }
}

35.复杂链表的复制 #

35.复杂链表的复制