이 글에서는 연결 리스트의 k번째 노드를 모두 제거하는 방법을 설명합니다. k의 배수에 있는 모든 노드를 삭제해야 합니다. 즉, k, 2*k, 3*k 등의 위치에 있는 노드를 삭제해야 합니다.
Input : 112->231->31->41->54->63->71->85 k = 3 Output : 112->231->41->54->71->85 Explanation: As 3 is the k-th node after its deletion list would be : First iteration :112->231->41->54->63->71->85 Now we count from 41 the next kth node is 63 After the second iteration our list will become : 112->231->41->54->71->85 And our iteration continues like this. Input: 14->21->23->54->56->61 k = 1 Output: Empty list Explanation: All nodes need to be deleted
이 문제에서는 최적화할 필요가 없을 정도로 충분히 효율적인 일반적인 접근 방식을 적용합니다.
해결책을 찾기 위한 접근 방식
이 문제에서는 카운터를 사용하여 연결 목록을 탐색합니다. 카운터가 k에 도달하면 해당 노드를 삭제하고 카운터를 새로 고쳐 현재 노드에서 k번째 위치의 다음 요소를 찾습니다.
예시
#include<bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
int data;
struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the data into the list
struct Node* new_n = new Node;
new_n->data = new_data;
new_n->next = (*ref);
(*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // delete function
if(prev == NULL) {
prev = curr;
curr = curr -> next;
free(prev);
prev = NULL;
} else {
prev -> next = curr -> next;
auto tmp = curr;
free(tmp); // freeing the space
}
}
/* Function to print linked list */
void displayList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
}
// Function to create a new node.
struct Node *newNode(int x) {
Node *temp = new Node;
temp->data = x;
temp->next = NULL;
return temp;
}
int main() {
struct Node* head = NULL;
push(&head, 80);
push(&head, 70);
push(&head, 60);
push(&head, 50);
push(&head, 40);
push(&head, 30);
push(&head, 20);
int k = 3; // given k
Node* curr = head; // current pointer
Node* prev = NULL; // previous pointer
int count = 1; // position counter
if(head == NULL || k == 0) // if list is already empty or k = 0
cout << "Invalid\n";
else {
while(curr) { // traversing the list
if(count == k) {
deletek(prev, curr);
curr = prev -> next;
count = 1;
} else {
count++;
prev = curr;
curr = curr -> next;
}
}
displayList(head); // printing the new list
}
return 0;
} 출력
20 30 50 60 80
위의 접근 방식은 O(N)의 시간 복잡도를 갖습니다. , 여기서 N은 주어진 연결 목록의 크기입니다.
위 코드 설명
위의 접근 방식에서 우리는 세 가지를 먼저 손에 들고 있습니다. 현재 포인터, 두 번째로 이전 포인터, 세 번째로 위치 카운터입니다. 이제 위치 카운터가 같을 때 일부 노드를 삭제합니다. 이전 및 현재 카운터를 매개변수로 사용하여 삭제하는 함수를 호출한다는 것을 알 수 있습니다. 이제 현재 노드를 삭제하고 이제 삭제 기능이 완료되면 공간을 확보합니다. 이제 현재 포인터를 다음으로 이동합니다. 다음 요소를 만들고 카운터를 1로 새로 고치고 현재가 NULL이 될 때까지 이 블록을 반복합니다.
결론
이 기사에서는 연결 목록의 모든 k 번째 노드를 제거하는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결한 완전한 접근 방식( Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.