FastPrep
Problem · Linked List

Deep Copy a Singly Linked List

Learn this problem
● MediumSuperhuman logoSuperhumanFULLTIMEPHONE SCREEN

Problem statement

Given the head head of a singly linked list, create a deep copy whose nodes share no identity with the original list.

For this exercise, after the copy is complete, change the value of the original node at zero-based position mutationIndex to newValue. Return an array containing two heads in this order:

  1. the mutated original list;
  2. the independent copy, which must still contain every value from before the mutation.

Function

copyAndMutateList(head: ListNode, mutationIndex: int, newValue: int) → ListNode[]

Examples

Example 1

head = [4,7,9]mutationIndex = 1newValue = 70return = [[4,70,9],[4,7,9]]

The value 7 in the original becomes 70. The copied list keeps 7, proving that its nodes are independent.

Example 2

head = [5]mutationIndex = 0newValue = -5return = [[-5],[5]]

Mutating the only original node does not change the one-node copy.

Example 3

head = [1,1,2,1]mutationIndex = 3newValue = 8return = [[1,1,2,8],[1,1,2,1]]

Repeated values do not affect node identity. Only the last original node changes.

Constraints

  • 1 <= number of nodes <= 10^4.
  • 0 <= mutationIndex < number of nodes.
  • -10^9 <= node.val, newValue <= 10^9.
  • The input list is finite and contains no cycle.

More Superhuman problems

drafts saved locally
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode next;
 * }
 */
public ListNode[] copyAndMutateList(ListNode head, int mutationIndex, int newValue) {
  // write your code here
}
head[4,7,9]
mutationIndex1
newValue70
expected[[4,70,9],[4,7,9]]
checking account