Copy List with Random Pointer — LeetCode 138 Python Solution
MediumHash TableLinked List
- Problem
- #138
- Pattern
- Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The problem
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list.
Example
- Input
- head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
- Output
- [[7,null],[13,0],[11,4],[10,2],[1,0]]
Python solution
Python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
d = {}
dummy = tail = Node(0)
cur = head
while cur:
node = Node(cur.val)
tail.next = node
tail = tail.next
d[cur] = node
cur = cur.next
cur = head
while cur:
d[cur].random = d[cur.random] if cur.random else None
cur = cur.next
return dummy.nextComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 138. Copy List with Random Pointer is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
On study lists
This problem is on NeetCode 150 and Top Interview 150.
Frequently asked questions
- How hard is LeetCode 138. Copy List with Random Pointer?
- LeetCode 138. Copy List with Random Pointer is rated Medium on LeetCode.
- What is the time complexity of LeetCode 138. Copy List with Random Pointer?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 138. Copy List with Random Pointer?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 138. Copy List with Random Pointer cover?
- LeetCode 138. Copy List with Random Pointer is tagged Hash Table and Linked List on LeetCode.