Medium

Len Chen
1 min readSep 19, 2018

Problem

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.

Solution

The Difficulty of this problem is how can we correctly assign random pointer before we haven’t visited it. You may use a hash table for saving all nodes of this linked list but it will cost more O(n) space for saving node information.

Here we are going to use a trick to make assigning random pointer be easier.

  1. Traverse entire list and make copies of each node, and make each copy at the next node of original one.
  2. Traverse entire list again. If there is an original node whose random pointer has value, set its copy node which is in the next field to be its random pointer’s next field, which is node.next.random = node.random.next.
  3. Traverse entire list last time and use strategy for solving #328 to reattach link between odd and even position.

Complexity

It’s clear that we traverse entire list three times so time complexity is O(n+n+n) = O(n) if n denotes to amount of nodes in list.

Because we make copies for each nodes in list, it will take O(n) extra space for saving copy nodes. But it doesn’t need to maintain a hash table for node information.

--

--

Len Chen
Len Chen

Responses (1)