Linked List는 각 노드에 두 개의 블록이 있는 선형 데이터 구조로, 한 블록에는 노드의 값 또는 데이터가 포함되고 다른 블록에는 다음 필드의 주소가 포함됩니다.
각 노드에 목록의 다른 노드를 가리키는 임의의 포인터가 포함된 연결 목록이 있다고 가정해 보겠습니다. 작업은 원본 목록과 동일한 목록을 구성하는 것입니다. 임의의 포인터가 있는 원본 목록에서 목록을 복사하는 것을 연결 목록의 'Deep Copy'라고 합니다.
예를 들어
입력-1
출력:
5-> 2 -> 3 -> 7 ->4 ->
설명: 주어진 연결 목록의 원래 노드 값으로 새 목록을 추가하고 원래 연결 목록의 임의 포인터를 새 목록의 다음 노드로 바꾸면 5-> 2->3 ->이 됩니다. 7-> 4->
이 문제를 해결하기 위한 접근 방식
데이터와 임의 포인터를 포함하는 노드가 있는 연결 목록이 있습니다. 데이터 및 임의 포인터가 있는 연결 목록의 복사본을 얻으려면 먼저 각 노드 뒤에 동일한 값을 가진 새 노드를 추가합니다. 이렇게 하면 각 노드 뒤에 중복 노드가 생성됩니다.
초기화 후 목록에서 임의의 포인터의 경로를 확인하고 새로 생성된 노드에 그에 따라 임의의 포인터를 배치합니다.
이제 원래 목록의 각 노드 다음에 새로 생성된 노드를 분리하면 연결 목록의 전체 복사본이 생성됩니다.
- 데이터 필드가 있는 연결 목록과 임의 노드의 주소에 대한 포인터를 가져옵니다.
- copyRandomList(listnode*head) 함수는 원본 목록의 헤드 노드를 입력으로 사용하고 목록의 전체 복사본을 반환합니다.
- 머리가 비어 있으면 목록도 비어 있고 머리도 반환해야 합니다.
- 이제 원래 목록의 각 노드 뒤에 동일한 값을 가진 새 노드를 삽입합니다.
- 그런 다음 원본 목록에서 임의의 포인터를 복사하고 새 노드를 삽입합니다. 즉, newnode->next =curr->randomPointer
- 포인터와 데이터로 새 노드가 생성되면 목록을 분리하고 목록을 출력으로 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
struct listnode {
int data;
listnode * next, * random;
listnode(int d) {
data = d;
next = NULL;
random = NULL;
}
};
void print(listnode * head) {
listnode * curr = head;
while (curr) {
cout << curr -> data << " " << curr -> random -> data << endl;
curr = curr -> next;
}
}
listnode * copyRandomList(listnode * head) {
if (!head) {
return head;
}
//Insert a new node with the same value after each node in the original list.
listnode * curr = head;
while (curr) {
listnode * newHead = new listnode(curr -> data);
newHead -> next = curr -> next;
curr -> next = newHead;
curr = curr -> next -> next;
}
//Now place the randompointer with the newly created node.
curr = head;
while (curr) {
if (curr -> random)
(curr -> next) -> random = (curr -> random) -> next;
curr = curr -> next -> next;
}
//Now Let us separate the newly created list
curr = head;
listnode * result = curr -> next;
listnode * dummyHead = new listnode(-1);
dummyHead -> next = result;
while (curr) {
curr -> next = result -> next;
curr = curr -> next;
if (curr) {
result -> next = curr -> next;
}
result = result -> next;
}
result = dummyHead -> next;
delete dummyHead;
return result;
}
int main() {
listnode * head = new listnode(5);
head -> next = new listnode(6);
head -> next -> next = new listnode(3);
head -> next -> next -> next = new listnode(4);
head -> next -> next -> next -> next = new listnode(2);
head -> random = head -> next -> next;
head -> next -> random = head;
head -> next -> next -> random =
head -> next -> next -> next -> next;
head -> next -> next -> next -> random =
head -> next -> next -> next -> next;
head -> next -> next -> next -> next -> random =
head -> next;
cout << "Original list :" << endl;
print(head);
cout << "Deep Copy of the List:" << endl;
listnode * deep_copyList = copyRandomList(head);
print(deep_copyList);
return 0;
} 위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.
출력
Original List: 5 3 6 5 3 2 4 2 2 6 Deep Copy of the List: 5 3 6 5 3 2 4 2 2 6