資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學刪除連結串列中每隔 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，我們刪除該節點並將計數器重置為 1，以查詢從當前節點開始的下一個第 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 等其他語言編寫相同的程式。我們希望您覺得這篇文章有所幫助。
更新於：2021年11月26日
437 次瀏覽
廣告