[LeetCode] Copy List with Random Pointer

문제

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.

 

Example 1:

Input: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

 

Note:

1. You must return the copy of the given head as a reference to the cloned list.

Approach

이 문제에서 까다로운 부분은 random pointer까지 deep copy해서 링크드리스트를 새로 만들어야 하는 것이다

즉 새로만든 링크드리스트의 random pointer가 가리키는 노드도 새로운 링크드리스트의 노드여야지

원래 있던 링크드리스트를 참조하면 안된다는 것.

따라서 어떤 포인터가 어떤 포인터를 가리키는지에 대한 정보를 따로 저장해야하며

복사 뿐 아니라 원래 주어진 링크드리스트의 값과 포인터도 그대로 보존해야 한다.

 

이 참조 관계를 저장하기 위해 문제에 주어진 힌트를 참고하여

map등의 hash를 쓰지 않고 원래 링크드리스트 노드 뒤에 새로운 링크드리스트의 노드를 달아놓는 방식으로 구현했다.

즉 원래 리스트가 A->B->C->D였다면

새로운 노드를 만들고 값을 복사해 A->A'->B->B'->C->C'->D->D' 이런식으로 달아 놓는식.

 

우선 리스트를 순회하며 새로운 노드를 만들고 값을 복사해 원래 노드 뒤에 달아놓는다.

그 후 새롭게 만들어진 리스트를 한번 더 순회하며 random 포인터가 가리키는 노드도 새로 만든 노드에 복사한다.

예를 들어 A의 랜덤포인터를 복사한다면 A->next->random = A->random->next 이런식.

원래 노드 뒤에 새로 복사된 노드가 달려 있다는 것을 이용한다. 

 

그 후 원래 리스트와 새로운 리스트를 분리해준다.

여기서 잘 안되서 시간 좀 많이 썼음.

 

시간복잡도는 O(n), 공간복잡도는 O(1)

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_CopyListWithRandomPointer.cpp

chi3236/algorithm