138. Copy List with Random Pointer

문제링크: https://leetcode.com/problems/copy-list-with-random-pointer/description/

Random pointer 가 포함된 연결 리스트를 deepcopy로 복사하는 문제다. Random pointer는 해당 연결 리스트의 랜덤한 지정을 가르키고 있으며 deepcopy 시에 복사된 리스트를 가르켜야 한다.

Solution

Address Map & Copy Recursion

연결 리스트의 deep copy 는 재귀를 통해 O(n)의 시간 복잡도로 만들 수 있다. 이 과정 도중에는 아직 미완성된 list를 가르키는 Random pointer(이하 RP)를 연결할 수 없다. 따라서 RP를 제외한 next 포인터를 이용해 deepcopy를 완성한다.

RP를 연결하기 위해선 오리지널 연결 노드에 대응하는 새 노드의 주소가 각각 필요하다. 이를 Map을 통해 기존 노드 주소 => 새 노드 주소의 형태로 저장한다면 다시 기존 리스트를 탐색하며 RP를 연결하려고 할 때 이를 이용해 새 리스트의 주소를 O(1)의 시간 복잡도로 얻어 바로 연결할 수 있다.

Alogorithm

• 재귀를 통해 머리를 copiedHead로 하는 새 리스트를 만든다.
• 만들면서 기존 노드의 주소에 대응하는 새 노드의 주소를 addressMap에 저장한다
• 두 노드를 다시 순회하면서 기존 노드의 random 주소를 통해 새 노드의 random주소를 얻어 random노드를 연결한다.

Code

var copyRandomList = function(head) {
  // Copy linked list with address map(original address => new node address)
  const addressMap = new Map();
  const copyLinkedList = (node) => {
    if (node === null) return null;
    const nextNode = copyLinkedList(node.next);
    const copiedNode = new Node(node.val, nextNode, null);
    addressMap.set(node, copiedNode);
    return copiedNode;
  }


  // Copy
  const copiedHead = copyLinkedList(head);

  // Connect random node with address map
  let curHead = head;
  let curCopiedHead = copiedHead;
  while (curHead && curCopiedHead) {
    curCopiedHead.random = addressMap.get(curHead.random);
    curHead = curHead.next;
    curCopiedHead = curCopiedHead.next;
  }

  return copiedHead;
};

리스트를 두 번 순회하는데 O(n)의 시간 복잡도, addressMap에 의해 O(n)의 공간 복잡도가 소요된다.