Copy List with Random Pointer

Question

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.

Thoughts

Solution 1

所有的类似deep copy的题目，传统做法是用一个hashtable, 先按照正常的方法复制，这一次新node的random pointer是指向旧node的random pointer指向的地方 复制的时候用hashtable记录下random pointer， 旧node为key,新node为value, 这样在下一次遍历时就可以将新node的random pointer指到新的node

time conplexity: O(n), space complexity: O(n)

Solution 2

space complexity: O(1)

1遍遍历，copy每一个node, random pointer依旧指向原来的点 2遍遍历，偶数的node的random pointer应该是指向目前point的node.next 3遍遍历，将这个list 分开

Solution

方法1 hashtable

# Definition for singly-linked list with a random pointer.
# class RandomListNode:  
#     def __init__(self, x):
#         self.label = x 
#         self.next = None  
#         self.random = None
class Solution:          
    # @param head: A RandomListNode
    # @return: A RandomListNode
    def copyRandomList(self, head):
        # write your code here
        hashTable = {}   
        dummy = RandomListNode(0)
        prev = dummy     
        while head:      
            newNode = RandomListNode(head.label)
            newNode.random = head.random
            hashTable[head] = newNode
            prev.next = newNode

            prev = prev.next
            head = head.next

        prev = dummy.next
        while prev:      
            if prev.random:
                prev.random = hashTable[prev.random]
            prev = prev.next
        return dummy.next

方法2

class Solution2:
    # @param head: A RandomListNode
    # @return: A RandomListNode
    def copyRandomList(self, head):
        # write your code here
        if not head:
            return head
        curr = head
        #copy every node and insert after
        while curr:
            tmp = curr.next
            newNode = RandomListNode(curr.label)
            newNode.random = curr.random
            curr.next = newNode
            newNode.next = tmp
            curr = tmp

        self.printList(head)

        #change random pointers of new nodes
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next

        self.printList(head)
        #split
        curr = head
        newHead = curr.next
        while curr:
            tmp = curr.next.next
            n = curr.next
            curr.next = tmp
            if n.next:
                n.next = n.next.next
            curr = curr.next                                                                                                              
        return newHead