Delete continuous nodes with sum K from a given linked list
Given a singly linked list and an integer K, the task is to remove all the continuous set of nodes whose sum is K from the given linked list. Print the updated linked list after the removal. If no such deletion can occur, print the original Linked list.
Examples:
Input: Linked List: 1 -> 2 -> -3 -> 3 -> 1, K = 3
Output: -3 -> 1
Explanation:
The nodes with continuous sum 3 are:
1) 1 -> 2
2) 3
Therefore, after removing these chain of nodes Linked List becomes: -3-> 1
Input: Linked List: 1 -> 1 -> -3 -> -3 -> -2, K = 5
Output: 1 -> 1 -> -3 -> -3 -> -2
Explanation:
No continuous nodes exits with sum K
Approach:
- Append Node with value zero at the starting of the linked list.
- Traverse the given linked list.
- During traversal store the sum of the node value till that node with the reference of the current node in an unordered_map.
- If there is Node with value (sum – K) present in the unordered_map then delete all the nodes from the node corresponding to value (sum – K) stored in map to the current node and update the sum as (sum – K).
- If there is no Node with value (sum – K) present in the unordered_map, then stored the current sum with node in the map.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // A Linked List Node struct ListNode { int val; ListNode* next; // Constructor 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; } cout << head->val; } // Function that removes continuous 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 sum is found with k, we would be needed // to delete the head node // so we need a reference pointer to its next ListNode* headNext = head->next; // If found value with (sum - K) if (umap.find(sum - K) != umap.end()) { ListNode* prev = umap[sum - K]; ListNode* start = prev; // Update sum sum = sum - K; int aux = sum; // move prev to the first node which need to deleted in nodes with sum K prev = prev->next; // Traverse till current head while (prev != head) { // temp will store the prev node address to free it from memory ListNode* temp = prev; aux += prev->val; if (prev != head) { umap.erase(aux); } prev = prev->next; delete temp; } // Update the start value to // the next value of current head delete head; start->next = headNext; } // If (sum - K) value not found else if (umap.find(sum) == umap.end()) { umap[sum] = head; } head = headNext; } // 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 if (head != NULL) printList(head); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; // A Linked List Node class ListNode { int val; ListNode next; // Constructor ListNode( int val) { this .val = val; this .next = null ; } } class GFG { // Function to create Node static ListNode getNode( int data) { ListNode temp = new ListNode(data); return temp; } // Function to print the Linked List static void printList(ListNode head) { while (head.next != null ) { System.out.print(head.val + " -> " ); head = head.next; } System.out.print(head.val); } // Function that removes continuous nodes // whose sum is K static 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 Map<Integer, ListNode> umap = new HashMap<Integer, ListNode>(); umap.put( 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.containsKey(sum - K)) { ListNode prev = umap.get(sum - K); ListNode start = prev; // Delete all the node // traverse till current node int aux = sum; // Update sum sum = sum - K; // Traverse till current head while (prev != head) { prev = prev.next; aux += prev.val; if (prev != head) { umap.remove(aux); } } // Update the start value to // the next value of current head start.next = head.next; } // If (sum - K) value not found else if (!umap.containsKey(sum)) { umap.put(sum, head); } head = head.next; } // Return the value of updated // head node return root.next; } // Driver code public static void main(String[] args) { // 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 if (head != null ) printList(head); } } // This code is contributed by jitin. |
Python3
# Python3 program for the above approach # A Linked List Node class ListNode: def __init__( self , val): self .val = val self . next = None # Function to create Node def getNode(data): temp = ListNode(data) temp. next = None return temp # Function to print the Linked List def printList(head): while (head. next ): print (head.val, end = ' -> ' ) head = head. next print (head.val, end = '') # Function that removes continuous nodes # whose sum is K def removeZeroSum(head, K): # Root node initialise to 0 root = ListNode( 0 ) # Append at the front of the given # Linked List root. next = head # Map to store the sum and reference # of the Node umap = dict () umap[ 0 ] = root # To store the sum while traversing sum = 0 # Traversing the Linked List while (head ! = None ): # Find sum sum + = head.val # If found value with (sum - K) if (( sum - K) in umap): prev = umap[ sum - K] start = prev # Delete all the node # traverse till current node aux = sum # Update sum sum = sum - K # Traverse till current head while (prev ! = head): prev = prev. next aux + = prev.val if (prev ! = head): umap.remove(aux) # Update the start value to # the next value of current head start. next = head. next # 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 if __name__ = = '__main__' : # 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 K = 5 # Function call to get head node # of the updated Linked List head = removeZeroSum(head, K) # Print the updated Linked List if (head ! = None ): printList(head) # This code is contributed by pratham76 |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; // A Linked List Node class ListNode { public int val; public ListNode next; // Constructor public ListNode( int val) { this .val = val; this .next = null ; } } class GFG { // Function to create Node static ListNode getNode( int data) { ListNode temp = new ListNode(data); return temp; } // Function to print the Linked List static void printList(ListNode head) { while (head.next != null ) { Console.Write(head.val + " -> " ); head = head.next; } Console.Write(head.val); } // Function that removes continuous nodes // whose sum is K static 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 Dictionary< int , ListNode> umap = new Dictionary< int , ListNode>(); umap.Add(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.ContainsKey(sum - K)) { ListNode prev = umap[sum - K]; ListNode start = prev; // Delete all the node // traverse till current node int aux = sum; // Update sum sum = sum - K; // Traverse till current head while (prev != head) { prev = prev.next; aux += prev.val; if (prev != head) { umap.Remove(aux); } } // Update the start value to // the next value of current head start.next = head.next; } // If (sum - K) value not found else if (!umap.ContainsKey(sum)) { umap.Add(sum, head); } head = head.next; } // Return the value of updated // head node return root.next; } // Driver code public static void Main( string [] args) { // 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 if (head != null ) printList(head); } } // This code is contributed by rutvik_56 |
Javascript
<script> // JavaScript program for the above approach // A Linked List Node class ListNode{ constructor(val){ this .val = val this .next = null } } // Function to create Node function getNode(data){ let temp = new ListNode(data) temp.next = null return temp } // Function to print the Linked List function printList(head){ while (head.next){ document.write(head.val, ' -> ' ) head = head.next } document.write(head.val, '' ) } // Function that removes continuous nodes // whose sum is K function removeZeroSum(head, K){ // Root node initialise to 0 let 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 let umap = new Map(); umap.set(0,root) // To store the sum while traversing let sum = 0 // Traversing the Linked List while (head != null ){ // Find sum sum += head.val // If found value with (sum - K) if (umap.has(sum - K) == true ){ let prev = umap.get(sum - K) let start = prev // Delete all the node // traverse till current node let aux = sum // Update sum sum = sum - K // Traverse till current head while (prev != head){ prev = prev.next aux += prev.val if (prev != head) umap. delete (aux) } // Update the start value to // the next value of current head start.next = head.next } // If (sum - K) value not found else umap.set(sum,head) head = head.next } // Return the value of updated // head node return root.next } // Driver Code // Create Linked List let 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 let K = 5 // Function call to get head node // of the updated Linked List head = removeZeroSum(head, K) // Print the updated Linked List if (head != null ) printList(head) // This code is contributed by shinjanpatra </script> |
1 -> 2 -> -3 -> 3 -> 1
Time Complexity: O(N), where N is the number of Node in the Linked List.
Auxiliary Space Complexity: O(N), where N is the number of Node in the Linked List.
Contact Us