[LeetCode-Swift] 138. Copy List with Random Pointer

문제 설명

Random Pointer가 있는 Linked List가 있는데 이를 완전 복사를 해서 새로운 Linked List로 만들라

• 이것만 보면 쉬운 문제 같은데 문제는 random 포인터 때문에 어려워졌다.
• 일반적으로 Linked List에서 Node는 Next 포인터 하나가 다음 노드를 가리키고 있다.
• 이 문제에서는 Random이라는 포인터가 추가로 주어짐

풀이

총 3단계로 풀이를 함

1. 첫번째 while-loop에서 복사를 한 새로운 Node를 기존 링크드리스트 노드들의 사이에 생성한다.
   1. 1-1-2-2-3-3-4-4
   2. random: 1→3, 2→4
2. 두번째 while-loop에서 복사한 노드들의 random 포인터를 복사한 노드로 연결한다.
   1. 1-1-2-2-3-3-4-4
   2. random: 1→3, 2→4
   3. copy random: 1→3, 2→4
3. 세번째 while-loop에서 반환할 변수, 반복문을 돌 변수, copy 리스트를 볼 변수 3개를 선언해서 돌면서 추출한다.

그림으로 보면 다음과 같다.

 

코드 예시

 

소감

• 코드를 봐서 이해가 안되는 때는 빨리 그림을 그리자.
• 답지 코드를 봤는데 그래도 이해가 안갔다. 한 3일 고민한듯

출처

• https://leetcode.com/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150