Brute force if you cannot figure out others' awesome anwer. O(n2)


  • 0
    Z

    pretty straightforward.

    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null) return null;
            RandomListNode copy = new RandomListNode(head.label);
            RandomListNode dummyCopy = new RandomListNode(0);
            RandomListNode dummyHead = new RandomListNode(0);
            dummyCopy.next = copy;
            dummyHead.next = head;
            while (head.next != null) {
                copy.next = new RandomListNode(head.next.label);
                copy = copy.next;
                head = head.next;
                
            }
            copy = dummyCopy.next;
            head = dummyHead.next;
            while (head != null) {
                if (head.random != null) {
                    int rand = head.random.label;
                    RandomListNode curr = dummyCopy.next;
                    while (curr != null) {
                        if (curr.label == rand) {
                            copy.random = curr;
                            break;
                        }
                        curr = curr.next;
                    }
                } else {
                    copy.random = null;
                }
                copy = copy.next;
                head = head.next;
            }
            return dummyCopy.next;
        }
    }
    

Log in to reply
 

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