signed

QiShunwang

“诚信为本、客户至上”

Leetcode 138. Copy List with Random Pointer

2020/12/27 3:48:56   来源:

在这里插入图片描述
方法1: 这题我没看懂题目什么叫deep copy。其实就是创建一个和input一模一样的list。第一个方法是lc官方解答1,是借助了一个map。我这个方法其实没怎么看,其实还没怎么搞清楚,推荐看lc的官方解答1,说的挺好。时间复杂n。空间复杂n。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    HashMap<Node, Node> visited = new HashMap();
    
    private Node getClonedNode(Node node){
        if(node != null){
            if(visited.containsKey(node)){
                return visited.get(node);
            }else{
                visited.put(node, new Node(node.val, null, null));
                return visited.get(node);
            }
        }
        return null;
    }
    
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        
        Node oldNode = head;
        Node newNode = new Node(oldNode.val);
        visited.put(oldNode, newNode);
        
        while(oldNode != null){
            newNode.random = getClonedNode(oldNode.random);
            newNode.next = getClonedNode(oldNode.next);
            oldNode = oldNode.next;
            newNode = newNode.next;
        }
        return visited.get(head);
        
    }
}

方法2: 非常巧妙的一个方法,不过没做过原题肯定想不到。时间复杂度n。空间1.

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node curr = head;
        while(curr != null){
            //Node nextNode = curr.next;
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }
        
        Node temp = head;
        int n = 1;
        Node prev = head;
        while(temp != null){
            if(n%2 == 0){
                if(prev.random == null){
                    temp.random = null;
                }else{
                    temp.random = prev.random.next;
                }
                prev = temp.next;  
            }
            temp = temp.next;
            n++;
        }
        
        Node temp1 = head; // old list
        Node res = head.next; // new list
        Node head_old = head.next;
        while(temp1 != null && temp1.next != null){
            Node cloned = temp1.next; 
            Node next = res.next;
            temp1.next = cloned.next;
            if(next == null){
                res.next = null;
                break;
            }else{
                res.next = next.next;
            }
            temp1 = temp1.next;
            res = res.next;
        }
        
        return head_old;
    }
}

总结: