138. Copy List with Random Pointer

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.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• 10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• The number of nodes will not exceed 1000.

Problem Summary

Given a linked list, each node contains an additional random pointer, which can point to any node in the linked list or to a null node. Return a deep copy of this linked list.

We use a linked list consisting of n nodes to represent the linked list in the input/output. Each node is represented by a [val, random_index]:

• val: an integer representing Node.val.
• random_index: the index of the node pointed to by the random pointer (range from 0 to n-1); if it does not point to any node, it is null.

Solution Approach

• Strictly speaking, this is a data structure problem. Given the data structure, perform a deep copy of it.

• First copy each node once and place the copy as its next node. In this way, create an interleaved copy of the linked list.

  Then make the random pointers of the interleaved linked list point to the correct positions.

  Then make the next pointers of the interleaved linked list point to the correct positions. Finally, separate the head nodes of these two intertwined linked lists, and the 2 linked lists can be separated.

Code

package leetcode

// Node define
type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	tempHead := copyNodeToLinkedList(head)
	return splitLinkedList(tempHead)
}

func splitLinkedList(head *Node) *Node {
	cur := head
	head = head.Next
	for cur != nil && cur.Next != nil {
		cur.Next, cur = cur.Next.Next, cur.Next
	}
	return head
}

func copyNodeToLinkedList(head *Node) *Node {
	cur := head
	for cur != nil {
		node := &Node{
			Val:  cur.Val,
			Next: cur.Next,
		}
		cur.Next, cur = node, cur.Next
	}
	cur = head
	for cur != nil {
		if cur.Random != nil {
			cur.Next.Random = cur.Random.Next
		}
		cur = cur.Next.Next
	}
	return head
}