연결리스트의 모든 K번째 노드 삭제

이 글에서는 연결리스트의 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은 주어진 연결 목록의 크기입니다.

위 코드 설명

위 방법에서는 먼저 세 가지를 유지합니다. 첫 번째는 현재 포인터, 두 번째는 이전 포인터, 세 번째는 위치 카운터입니다. 이제 위치 카운터가 k와 같을 때 특정 노드를 삭제하고 삭제 함수를 호출하고 이전 및 현재 카운터를 매개변수로 전달한 다음 현재 노드를 삭제하고 공간을 확보합니다. 삭제 함수가 완료되면 이동합니다. 현재 포인터 다음 요소로 이동하여 카운터를 1로 새로 고치고 현재 포인터가 NULL이 될 때까지 이 블록을 반복합니다.

결론

이 글에서는 연결 리스트의 k번째 노드를 모두 삭제하는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 완전한(사소한) 접근 방식을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 연결리스트의 모든 K번째 노드 삭제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!