My accepted Java code. O(n) but need to iterate the list 3 times


  • 42
    S

    The idea is:
    Step 1: create a new node for each existing node and join them together
    eg: A->B->C will be A->A'->B->B'->C->C'

    Step2: copy the random links: for each new node n', n'.random = n.random.next

    Step3: detach the list: basically n.next = n.next.next; n'.next = n'.next.next

    Here is the code:

    /**
     * Definition for singly-linked list with a random pointer.
     * class RandomListNode {
     *     int label;
     *     RandomListNode next, random;
     *     RandomListNode(int x) { this.label = x; }
     * };
     */
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if(head==null){
                return null;
            }
            RandomListNode n = head;
            while (n!=null){
                RandomListNode n2 = new RandomListNode(n.label);
                RandomListNode tmp = n.next;
                n.next = n2;
                n2.next = tmp;
                n = tmp;
            }
            
            n=head;
            while(n != null){
                RandomListNode n2 = n.next;
                if(n.random != null)
                    n2.random = n.random.next;
                else
                    n2.random = null;
                n = n.next.next;
            }
            
            //detach list
            RandomListNode n2 = head.next;
            n = head;
            RandomListNode head2 = head.next;
            while(n2 != null && n != null){
                n.next = n.next.next;
                if (n2.next == null){
                    break;
                }
                n2.next = n2.next.next;
                
                n2 = n2.next;
                n = n.next;
            }
            return head2;
            
        }
    }

  • 6
    V

    Using a HashMap and there are n recursive calls.

    public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode,RandomListNode> nodemap = new HashMap<RandomListNode,RandomListNode>();
        return copyListHelper(head, nodemap);
    }
    public RandomListNode copyListHelper(RandomListNode head, HashMap<RandomListNode,RandomListNode> nodemap)  {
        if(head==null)  return null;
        if(nodemap.containsKey(head))  return nodemap.get(head);
        RandomListNode ret = new RandomListNode(head.label);
        nodemap.put(head,ret);
        ret.next = copyListHelper(head.next, nodemap);
        ret.random = copyListHelper(head.random,nodemap);
        return ret;
    }
    

  • 11
    B

    same idea but with concise hashmap code.

    public RandomListNode copyRandomList(RandomListNode head) {
    	//<original, clone>
        HashMap<RandomListNode, RandomListNode> maps = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode cursor = head;
        while(null != cursor){
            maps.put(cursor, new RandomListNode(cursor.label));
            cursor = cursor.next; 
        }
        cursor = head;
        while(null != cursor){
        	maps.get(cursor).random = maps.get(cursor.random);
        	cursor = cursor.next;
        }
        cursor = head;
        while(null != cursor){
        	maps.get(cursor).next = maps.get(cursor.next);
            cursor = cursor.next;
        }
        return maps.get(head);
    }

  • 1
    A

    I had something similar, but it gives a StackOverflow error. This answer is not accepted, even though it may well should be :-).


  • 1
    F

    Good method. But I think you don't need three iteration now, two is enough. We can set next and random in one iteration together.


  • 0
    H

    Stack overflow


  • 0

    What @flyinghx61 said is true. It can be done in two iterations.

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p = head;
        while (p != null) {
            map.put(p, new RandomListNode(p.label));
            p = p.next;
        }
    
        p = head;
        while (p!= null) {
            map.get(p).random = map.get(p.random);
            map.get(p).next = map.get(p.next);
            p = p.next;
        }
        return map.get(head);
    }

  • 0

    Using hashmap is surely simple, but it's inefficient to use an Object as key. I vote for the one without hashmap which runs much faster when testing. Here's my more concise and easy-to-understand Java code.

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        RandomListNode p = head;
        while (p != null) {
            RandomListNode pClone = new RandomListNode(p.label);
            pClone.next = p.next;
            p.next = pClone;
            p = pClone.next;
        }
    
        p = head;
        while (p != null) {
            p.next.random = p.random == null ? null : p.random.next;
            p = p.next.next;
        }
    
        RandomListNode headClone = head.next;
        p = head;
        while (p != null) {
            RandomListNode pClone = p.next;
            p.next = pClone.next;
            pClone.next = pClone.next == null ? null : pClone.next.next;
            p = p.next;
        }
        return headClone;
    }

  • 0
    C

    Brilliant solutions! Thanks for sharing!


  • 0
    F

    For the detach part, I tried to use the dummy node to make it easier. But I cannot even pass the first test case. Can anyone tell me why this happens?

    //detach
            RandomListNode dummy = new RandomListNode(0);
            dummy.next = head;
            head = dummy;
            while(head.next != null){
                head.next = head.next.next;
                head = head.next;
            }
            
            //get result
            return dummy.next;
    

  • 0
    J

    Why my below code got accepted by OJ since I did not use map and also not use three iterations with O(n). Any advises?

    public RandomListNode copyRandomList(RandomListNode head) {
    if(head == null){
    return null;
    }
    RandomListNode result = new RandomListNode(-1);
    RandomListNode current = new RandomListNode(head.label);
    result.next = current;

    	while(head != null){
    		if(head.next != null){
    			RandomListNode next = new RandomListNode(head.next.label);
    			current.next = next;
    		}else{
    			current.next = null;
    		}
    		if(head.random != null){
    			RandomListNode random = new RandomListNode(head.random.label);
    			current.random = random;
    		}else{
    			current.random = null;
    		}
    		head = head.next;
    		current = current.next;
    	}
    	return result.next;
    }

  • 0

    Why three or even two iterations? I could write it in one iteration:

    Brilliant Solution with only One Iteration - Using Dummy Node and Dictionary


  • 0

    @FreshMeYo Please see my below solution, where I have used Dummy node and solved the question in one iteration:

    Brilliant Solution with only One Iteration - Using Dummy Node and Dictionary


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.