Given head of a linked list of integers and an integer k, your task is to modify the linked list as follows:
- Consider nodes in groups of size k. In every group, replace value of first node with group sum.
- Also, delete the elements of group except the first node.
- During traversal, if the remaining nodes in linked list are less than k then also do the above considering remaining nodes.
Examples:
Input: N = 6, K = 2
1->2->3->4->5->6
Output: 3 7 11
We have denoted grouping of k elements by (). The elements inside () are summed.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
(1 -> 2) -> 3 -> 4 -> 5 -> 6 -> null
(3) -> 3 -> 4 -> 5 -> 6 -> null
3 -> (3 -> 4) -> 5 -> 6 -> null
3 -> (7) -> 5 -> 6 -> null
3 -> 7 -> (5 -> 6) -> null
3 -> 7 -> (11) -> null
3 -> 7 -> 11 -> null
Approach:
Insert the given nodes in the Linked list. The approach of insertion has been discussed in this post. Once the nodes are inserted, iterate from the beginning of the list. Mark the first node as temp node. Iterate for the next k-1 nodes and sum up the nodes in sum variable. If the number of nodes is less than K, then replace the temp node’s data with sum and point temp to NULL.
If there is a group with K nodes, replace the temp’s data with sum and move temp to the node which is just after K nodes. Continue the above operation till temp points to NULL. Once temp reaches the end, it means all groups of size K has been traversed and the node has been replaced with the sum of nodes of size K. Once the operation of replacements have been done, the linked list thus formed can be printed. The method of printing the linked list has been discussed in this post.
Below is the implementation of the above approach:
C++
// C++ program for// SP - K Sum#include <iostream>using namespace std;// structure for linked liststruct Node { long long data; Node* next;};// allocated new nodeNode* newNode(int key){ Node* temp = new Node; temp->data = key; temp->next = NULL; return temp;}// function to insert node in a Linked ListNode* insertNode(Node* head, int key){ if (head == NULL) head = newNode(key); else head->next = insertNode(head->next, key); return head;}// traverse the node// to print itvoid print(Node* head){ // traverse the linked list while (head) { cout << head->data << " "; head = head->next; } cout << endl;}// function to perform the following operationvoid KSum(Node* head, int k){ // initially pointing to start Node* temp = head; // iterate till end while (temp) { // dummy variable to store k long long count = k; // summation of nodes long long sum = 0; // currently at node from // which iteration is done Node* curr = temp; // till k nodes are visited and // last node is not visited while (count-- && curr) { // add to sum the node data sum = sum + curr->data; // move to the next node curr = curr->next; } // change pointer's data of temp to sum temp->data = sum; // move temp to next pointer temp->next = curr; // move temp to the next pointer temp = temp->next; }}// Driver Codeint main(){ Node* head = NULL; // inserts nodes in the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); int k = 2; // Function call to perform the // given operations KSum(head, k); // print the linked list print(head); return 0;} |
Java
// Java program for// SP - K Sumimport java.io.*;import java.util.*;// structure for linked listclass Node { int data; Node next; Node(int key) { data = key; next = null; }}class GFG{ // allocated new nodestatic Node head;// function to insert node// in a Linked Listpublic static Node insertNode(Node head, int key){ if (head == null) head = new Node(key); else head.next = insertNode(head.next, key); return head;}// traverse the node// to print itpublic static void print(Node head){ // traverse the linked list while (head != null) { System.out.print(head.data + " "); head = head.next; } System.out.println();}// function to perform // the following operationpublic static void KSum(Node head, int k){ // initially pointing // to start Node temp = head; // iterate till end while (temp != null) { // dummy variable // to store k int count = k; // summation of nodes int sum = 0; // currently at node from // which iteration is done Node curr = temp; // till k nodes are visited and // last node is not visited while (count > 0 && curr != null) { // add to sum the node data sum = sum + curr.data; // move to the next node curr = curr.next; count--; } // change pointer's data // of temp to sum temp.data = sum; // move temp to // next pointer temp.next = curr; // move temp to // the next pointer temp = temp.next; } //return temp;}// Driver Codepublic static void main(String args[]){ head = null; // inserts nodes in // the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); int k = 2; // Function call to perform // the given operations KSum(head, k); // print the linked list print(head);}} |
Python3
# Python program for# SP - K Sum# structure for linked listclass Node: def __init__(self, key): self.data = key self.next = None# function to insert node in a Linked Listdef insertNode(head: Node, key: int) -> Node: if head is None: head = Node(key) else: head.next = insertNode(head.next, key) return head# traverse the node# to print itdef Print(head: Node): # traverse the linked list while head: print(head.data, end = " ") head = head.next print()# function to perform the following operationdef KSum(head: Node, k: int): # initially pointing to start temp = head # iterate till end while temp: # dummy variable to store k count = k # summation of nodes sum = 0 # currently at node from # which iteration is done curr = temp # till k nodes are visited and # last node is not visited while count and curr: # add to sum the node data sum = sum + curr.data # move to the next node curr = curr.next count -= 1 # change pointer's data of temp to sum temp.data = sum # move temp to next pointer temp.next = curr # move temp to the next pointer temp = temp.next# Driver Codeif __name__ == "__main__": head = None # inserts nodes in the linked list head = insertNode(head, 1) head = insertNode(head, 2) head = insertNode(head, 3) head = insertNode(head, 4) head = insertNode(head, 5) head = insertNode(head, 6) k = 2 # Function call to perform the # given operations KSum(head, k) # print the linked list Print(head)# This code is contributed by# sanjeev2552 |
C#
// C# program for SP - K Sumusing System;// structure for linked listpublic class Node { public int data; public Node next; public Node(int key) { data = key; next = null; }}public class GFG{ // allocated new nodestatic Node head;// function to insert node// in a Linked Listpublic static Node insertNode(Node head, int key){ if (head == null) head = new Node(key); else head.next = insertNode(head.next, key); return head;}// traverse the node// to print itpublic static void print(Node head){ // traverse the linked list while (head != null) { Console.Write(head.data + " "); head = head.next; } Console.WriteLine();}// function to perform // the following operationpublic static void KSum(Node head, int k){ // initially pointing // to start Node temp = head; // iterate till end while (temp != null) { // dummy variable // to store k int count = k; // summation of nodes int sum = 0; // currently at node from // which iteration is done Node curr = temp; // till k nodes are visited and // last node is not visited while (count > 0 && curr != null) { // add to sum the node data sum = sum + curr.data; // move to the next node curr = curr.next; count--; } // change pointer's data // of temp to sum temp.data = sum; // move temp to // next pointer temp.next = curr; // move temp to // the next pointer temp = temp.next; } // return temp;}// Driver Codepublic static void Main(){ head = null; // inserts nodes in // the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); int k = 2; // Function call to perform // the given operations KSum(head, k); // print the linked list print(head);}}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // JavaScript program for SP - K Sum // structure for linked list class Node { constructor(key) { this.data = key; this.next = null; } } // allocated new node var head = null; // function to insert node // in a Linked List function insertNode(head, key) { if (head == null) head = new Node(key); else head.next = insertNode(head.next, key); return head; } // traverse the node // to print it function print(head) { // traverse the linked list while (head != null) { document.write(head.data + " "); head = head.next; } document.write("<br>"); } // function to perform // the following operation function KSum(head, k) { // initially pointing // to start var temp = head; // iterate till end while (temp != null) { // dummy variable // to store k var count = k; // summation of nodes var sum = 0; // currently at node from // which iteration is done var curr = temp; // till k nodes are visited and // last node is not visited while (count > 0 && curr != null) { // add to sum the node data sum = sum + curr.data; // move to the next node curr = curr.next; count--; } // change pointer's data // of temp to sum temp.data = sum; // move temp to // next pointer temp.next = curr; // move temp to // the next pointer temp = temp.next; } // return temp; } // Driver Code head = null; // inserts nodes in // the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); var k = 2; // Function call to perform // the given operations KSum(head, k); // print the linked list print(head); // This code is contributed by rdtank. </script> |
Output
3 7 11
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
