Search for a command to run...
Clone a singly linked list containing next and random pointers using O(1) extra space
Initial List
Starting deep copy of a linked list with random pointers.
O(1) Space Interleaving
1class Solution {2 // Insert a copy of each node in between the original nodes3 insertCopyInBetween(head) {4 let temp = head;5 while (temp !== null) {6 let nextElement = temp.next;7 let copy = new ListNode(temp.val);8 copy.next = nextElement;9 temp.next = copy;10 temp = nextElement;11 }12 }13 14 // Function to connect random pointers of the copied nodes15 connectRandomPointers(head) {16 let temp = head;17 while (temp !== null) {18 let copyNode = temp.next;19 if (temp.random !== null) {20 copyNode.random = temp.random.next;21 } else {22 copyNode.random = null;23 }24 temp = temp.next.next;25 }26 }27 28 // Function to retrieve the deep copy of the linked list29 getDeepCopyList(head) {30 let temp = head;31 let dummyNode = new ListNode(-1);32 let res = dummyNode;33 34 while (temp !== null) {35 res.next = temp.next;36 res = res.next;37 temp.next = temp.next.next;38 temp = temp.next;39 }40 return dummyNode.next;41 }42 //head: 743 // Function to clone the linked list44 copyRandomList(head) {45 if (!head) return null;46 47 this.insertCopyInBetween(head);48 this.connectRandomPointers(head);49 return this.getDeepCopyList(head);50 }51}