Cracking LeetCode: 138. Copy List with Random Pointer
May
11
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Thought:
Associate the original list and the copy list side by side, and after copying the random pointer, split the original list and the copy list.
Use O(1) extra space and O(n) time complexity.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
# Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution(object): def copyRandomList(self, head): """ :type head: RandomListNode :rtype: RandomListNode """ #copy node and link copy node and original node side-by-side iter = head while iter != None: copy = RandomListNode(iter.label) copy.next = iter.next iter.next = copy iter = copy.next #assign random pointer iter = head while iter != None: if iter.random: iter.next.random = iter.random.next iter = iter.next.next #extract original list and copy list: iter = head dummyHead = copyHead = RandomListNode(0) while iter != None: copyHead.next = iter.next copyHead = copyHead.next iter.next = copyHead.next iter = iter.next return dummyHead.next |
Reference:
Comments
Comments are closed.