从给定的链表中删除总和为K的连续节点。
原文：https://www.geeksforgeeks.org/delete-continuous-nodes-with-sum-k-from-a-given-linked-list/
给定单链表和整数K，任务是从给定的链表中删除总和为K的所有连续节点集。 删除后打印更新的链表。 如果无法进行此类删除，请打印原始的链表。
示例：
输入：
linkedList = 1 -> 2 -> 3 -> 3 -> 1, K = 3输出：
-3 -> 1解释：
连续和为 3 的节点为：
1）
1 -> 22）
3因此， 删除这些节点链的链表将变为：
-3 -> 1输入：
linkedList = 1 -> 1 -> -3 -> -3-> -2, K = 5输出：
1 -> 1 -> -3 -> -3 -> -2解释：
不存在总和为
K的连续节点
方法：
-
在链表的开头附加值为零的节点。
-
在遍历期间，将节点值的总和存储到该节点，并以
unordered_map作为当前节点的引用。 -
如果在
unordered_map中存在值为sum – K的节点，则删除映射中与存储的值sum – K对应的节点到当前节点的所有节点，并将和更新为0。 -
如果在
unordered_map中不存在sum – K值的节点，则将当前总和与节点存储在映射中。
下面是上述方法的实现：
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A Linked List Node
struct ListNode {
int val;
ListNode* next;
// Contructor
ListNode(int x)
: val(x), next(NULL)
{
}
};
// Function to create Node
ListNode* getNode(int data)
{
ListNode* temp;
temp = (ListNode*)malloc(sizeof(ListNode));
temp->val = data;
temp->next = NULL;
return temp;
}
// Function to print the Linked List
void printList(ListNode* head)
{
while (head->next) {
cout << head->val << " -> ";
head = head->next;
}
printf("%d", head->val);
}
// Function that removes continuos nodes
// whose sum is K
ListNode* removeZeroSum(ListNode* head,
int K)
{
// Root node initialise to 0
ListNode* root = new ListNode(0);
// Append at the front of the given
// Linked List
root->next = head;
// Map to store the sum and reference
// of the Node
unordered_map<int, ListNode*> umap;
umap[0] = root;
// To store the sum while traversing
int sum = 0;
// Traversing the Linked List
while (head != NULL) {
// Find sum
sum += head->val;
// If found value with (sum - K)
if (umap.find(sum - K) != umap.end()) {
ListNode* prev = umap[sum - K];
ListNode* start = prev;
// Delete all the node
// traverse till current node
int aux = sum;
// Traverse till current head
while (prev != head) {
prev = prev->next;
aux += prev->val;
if (prev != head) {
umap.erase(aux);
}
}
// Update the start value to
// the next value of current head
start->next = head->next;
// Update sum to zero
sum = 0;
}
// If (sum - K) value not found
else {
umap[sum] = head;
}
head = head->next;
}
// Return the value of updated
// head node
return root->next;
}
// Driver Code
int main()
{
// head Node
ListNode* head;
// Create Linked List
head = getNode(1);
head->next = getNode(2);
head->next->next = getNode(-3);
head->next->next->next = getNode(3);
head->next->next->next->next = getNode(1);
// Given sum K
int K = 5;
// Function call to get head node
// of the updated Linked List
head = removeZeroSum(head, K);
// Print the updated Linked List
printList(head);
return 0;
}
输出：
1 -> 2 -> -3 -> 3 -> 1
时间复杂度：O(n)，其中N是链表中节点的数目。
辅助空间复杂度：O(n)，其中N是链表中节点的数目。
如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 tribution.geeksforgeeks.org 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。
如果您发现任何不正确的地方，请单击下面的“改进文章”按钮，以改进本文。
版权属于：月萌API www.moonapi.com，转载请注明出处
