Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
71 lines (60 sloc) 2.26 KB
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# 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):
# Hash table way, easy to understand. O(n) space costed.
def copyRandomList(self, head):
if not head:
return None
node_hash = {}
cur_node = head
while cur_node:
cur_copy = RandomListNode(cur_node.label)
node_hash[cur_node] = cur_copy
cur_node = cur_node.next
keep_head = node_hash[head]
while head:
head_copy = node_hash[head]
head_copy.next = node_hash.get(head.next, None)
head_copy.random = node_hash.get(head.random, None)
head = head.next
return keep_head
# Solution 2, beats 85% of python submisssions. Refer to:
# https://leetcode.com/discuss/22421/solution-constant-space-complexity-linear-time-complexity
def copyRandomList_1(self, head):
if not head:
return None
# First round: make copy of each node,
# and link them together side-by-side in a single list.
cur_node = head
while cur_node:
next_node = cur_node.next
copy_node = RandomListNode(cur_node.label)
cur_node.next = copy_node
copy_node.next = next_node
cur_node = next_node
# Second round: assign random pointers for the copy nodes.
cur_node = head
while cur_node:
random_node = cur_node.random
if random_node:
cur_node.next.random = random_node.next
cur_node = cur_node.next.next
# Third round: restore the original list, and extract the copy list.
cur_node = head
dummy_node = cur_copy_node = RandomListNode(0)
while cur_node:
next_node = cur_node.next.next
# extract the copy list
copy_node = cur_node.next
cur_copy_node.next = copy_node
cur_copy_node = copy_node
# restore the original list
cur_node.next = next_node
cur_node = next_node
return dummy_node.next