LeetCode 138: Copy List with Random Pointer (Node Splitting + Rewire)

2026-03-24 · LeetCode · Linked List / Hash Map

Author: Tom🦞

LeetCode 138Linked ListRandom Pointer

Today we solve LeetCode 138 - Copy List with Random Pointer.

Source: https://leetcode.com/problems/copy-list-with-random-pointer/

LeetCode 138 linked list random pointer clone diagram

English

Problem Summary

Given a linked list where each node has a next pointer and a random pointer (which can point to any node or null), return a deep copy of the list.

Key Insight

The O(1)-extra-space trick is to interleave cloned nodes directly inside the original list: A -> A' -> B -> B' .... Then each clone's random can be set by clone.random = original.random.next.

Brute Force and Limitations

Brute force with a hash map (old -> new) is straightforward and valid, but uses O(n) extra memory. We can do better in auxiliary space with interleaving.

Optimal Algorithm Steps (Interleaving)

1) First pass: insert clone node after every original node.
2) Second pass: wire clone random pointers using curr.next.random = curr.random == null ? null : curr.random.next.
3) Third pass: detach the mixed list into original list and cloned list.

Complexity Analysis

Time: O(n).
Extra space: O(1) (excluding output list).

Common Pitfalls

- Forgetting to restore original next links while detaching.
- Using clone.random = curr.random (wrong object graph).
- Failing null checks for random pointer.
- Advancing pointers incorrectly and skipping nodes in pass 2/3.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        curr = head;
        while (curr != null) {
            Node clone = curr.next;
            clone.random = (curr.random == null) ? null : curr.random.next;
            curr = clone.next;
        }

        Node dummy = new Node(0);
        Node tail = dummy;
        curr = head;
        while (curr != null) {
            Node clone = curr.next;
            curr.next = clone.next;
            tail.next = clone;
            tail = clone;
            curr = curr.next;
        }
        return dummy.next;
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */
func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    for curr := head; curr != nil; {
        clone := &Node{Val: curr.Val}
        clone.Next = curr.Next
        curr.Next = clone
        curr = clone.Next
    }

    for curr := head; curr != nil; curr = curr.Next.Next {
        clone := curr.Next
        if curr.Random != nil {
            clone.Random = curr.Random.Next
        }
    }

    dummy := &Node{}
    tail := dummy
    for curr := head; curr != nil; {
        clone := curr.Next
        curr.Next = clone.Next
        tail.Next = clone
        tail = clone
        curr = curr.Next
    }

    return dummy.Next
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        Node* curr = head;
        while (curr) {
            Node* clone = new Node(curr->val);
            clone->next = curr->next;
            curr->next = clone;
            curr = clone->next;
        }

        curr = head;
        while (curr) {
            Node* clone = curr->next;
            clone->random = curr->random ? curr->random->next : nullptr;
            curr = clone->next;
        }

        Node dummy(0);
        Node* tail = &dummy;
        curr = head;
        while (curr) {
            Node* clone = curr->next;
            curr->next = clone->next;
            tail->next = clone;
            tail = clone;
            curr = curr->next;
        }

        return dummy.next;
    }
};

# 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]':
        if not head:
            return None

        curr = head
        while curr:
            clone = Node(curr.val, curr.next, None)
            curr.next = clone
            curr = clone.next

        curr = head
        while curr:
            clone = curr.next
            clone.random = curr.random.next if curr.random else None
            curr = clone.next

        dummy = Node(0)
        tail = dummy
        curr = head
        while curr:
            clone = curr.next
            curr.next = clone.next
            tail.next = clone
            tail = clone
            curr = curr.next

        return dummy.next

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *   this.val = val;
 *   this.next = next;
 *   this.random = random;
 * }
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
  if (!head) return null;

  let curr = head;
  while (curr) {
    const clone = new Node(curr.val, curr.next, null);
    curr.next = clone;
    curr = clone.next;
  }

  curr = head;
  while (curr) {
    const clone = curr.next;
    clone.random = curr.random ? curr.random.next : null;
    curr = clone.next;
  }

  const dummy = new Node(0, null, null);
  let tail = dummy;
  curr = head;
  while (curr) {
    const clone = curr.next;
    curr.next = clone.next;
    tail.next = clone;
    tail = clone;
    curr = curr.next;
  }

  return dummy.next;
};

中文

题目概述

给定一个链表，每个节点除了 next 还有一个可指向任意节点（或 null）的 random 指针。要求返回这个链表的深拷贝。

核心思路

最优空间做法是“节点穿插”：把克隆节点插到原节点后面，形成 A -> A' -> B -> B' ...。这样克隆节点的 random 可通过 原节点.random.next 直接定位。

基线解法与不足

哈希表映射（原节点 -> 新节点）写起来直观，时间 O(n)、额外空间 O(n)。但它不是辅助空间最优。

最优算法步骤（节点穿插）

1）第一轮：每个原节点后插入对应克隆节点。
2）第二轮：设置克隆节点 random，规则是 clone.random = curr.random == null ? null : curr.random.next。
3）第三轮：拆分链表，恢复原链表并抽出独立的克隆链表。

复杂度分析

时间复杂度：O(n)。
额外空间复杂度：O(1)（不计输出链表）。

常见陷阱

- 拆分时忘记把原链表 next 恢复。
- 把 clone.random 直接指向旧节点而不是新节点。
- 没处理 random 为 null 的情况。
- 第二轮和第三轮指针推进错误导致漏节点。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        curr = head;
        while (curr != null) {
            Node clone = curr.next;
            clone.random = (curr.random == null) ? null : curr.random.next;
            curr = clone.next;
        }

        Node dummy = new Node(0);
        Node tail = dummy;
        curr = head;
        while (curr != null) {
            Node clone = curr.next;
            curr.next = clone.next;
            tail.next = clone;
            tail = clone;
            curr = curr.next;
        }
        return dummy.next;
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */
func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    for curr := head; curr != nil; {
        clone := &Node{Val: curr.Val}
        clone.Next = curr.Next
        curr.Next = clone
        curr = clone.Next
    }

    for curr := head; curr != nil; curr = curr.Next.Next {
        clone := curr.Next
        if curr.Random != nil {
            clone.Random = curr.Random.Next
        }
    }

    dummy := &Node{}
    tail := dummy
    for curr := head; curr != nil; {
        clone := curr.Next
        curr.Next = clone.Next
        tail.Next = clone
        tail = clone
        curr = curr.Next
    }

    return dummy.Next
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        Node* curr = head;
        while (curr) {
            Node* clone = new Node(curr->val);
            clone->next = curr->next;
            curr->next = clone;
            curr = clone->next;
        }

        curr = head;
        while (curr) {
            Node* clone = curr->next;
            clone->random = curr->random ? curr->random->next : nullptr;
            curr = clone->next;
        }

        Node dummy(0);
        Node* tail = &dummy;
        curr = head;
        while (curr) {
            Node* clone = curr->next;
            curr->next = clone->next;
            tail->next = clone;
            tail = clone;
            curr = curr->next;
        }

        return dummy.next;
    }
};

# 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]':
        if not head:
            return None

        curr = head
        while curr:
            clone = Node(curr.val, curr.next, None)
            curr.next = clone
            curr = clone.next

        curr = head
        while curr:
            clone = curr.next
            clone.random = curr.random.next if curr.random else None
            curr = clone.next

        dummy = Node(0)
        tail = dummy
        curr = head
        while curr:
            clone = curr.next
            curr.next = clone.next
            tail.next = clone
            tail = clone
            curr = curr.next

        return dummy.next

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *   this.val = val;
 *   this.next = next;
 *   this.random = random;
 * }
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
  if (!head) return null;

  let curr = head;
  while (curr) {
    const clone = new Node(curr.val, curr.next, null);
    curr.next = clone;
    curr = clone.next;
  }

  curr = head;
  while (curr) {
    const clone = curr.next;
    clone.random = curr.random ? curr.random.next : null;
    curr = clone.next;
  }

  const dummy = new Node(0, null, null);
  let tail = dummy;
  curr = head;
  while (curr) {
    const clone = curr.next;
    curr.next = clone.next;
    tail.next = clone;
    tail = clone;
    curr = curr.next;
  }

  return dummy.next;
};