Given a linked list with some two adjacent repeating nodes before a zero, task is to double the first and make next 0. After this, append all the zeros to tail.
Prerequisite: Basics of implementation of Singly Linked List
Examples :
Input : 4 -> 4 -> 0 -> 2 -> 3 -> 4 ->
3 -> 3 -> 0 -> 4 ->
Output : 8-> 2-> 3-> 4-> 6-> 4-> 0->
0-> 0-> 0->
Explanation :
First, after doubling the first element and making
second element 0 before all zeros.
8 -> 0 -> 0 -> 2 -> 3 -> 4 -> 6 -> 0
-> 0 -> 4 ->
Next :
8 -> 6 -> 5 -> 6 -> 0 -> 0 -> 0 ->
0 -> 0 -> 0 -> 0 ->
Input : 0 -> 4 -> 4 -> 0 -> 3 -> 3 -> 0
-> 5 -> 0 -> 0 -> 6 ->
Output : 8 -> 6 -> 5 -> 6 -> 0 -> 0 -> 0
-> 0 -> 0 -> 0 -> 0 ->
Traverse through the linked list, and wherever there are two adjacent same data of nodes before a 0 (e.g. 4 -> 4 -> 0), then, double first element and make another as 0 (e.g. 8 -> 0 -> 0 ->). Finally, traverse the linked list and linearly point all the zeros to tail.
Implementation:
Java
// Java code to modify linked listimport java.util.*;// Linked List Nodeclass Node { int data; Node next; // Constructor public Node(int data) { this.data = data; next = null; }}// Class to perform operations// on linked listclass GfG { // Recursive function to double the one of two // elements and make next one as 0, // which are equal before 0 public static void changeTwoBefore0(Node head) { // there should be atleast three elements // to perform required operation if (head == null || head.next == null || head.next.next == null) return; // when two continuous elements // are same if ((head.data == head.next.data) && (head.next.next.data == 0)) { int temp = head.data; head.data = 2 * temp; head.next.data = 0; if (head.next.next.next != null) head = head.next.next.next; else return; } else head = head.next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head); } // function to append zeros at tail public static Node appendZero(Node head) { if (head == null || head.next == null) return head; // Find tail node Node tail = head; while (tail.next != null) tail = tail.next; Node origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. Node curr = head; while (curr.next != null && curr.data == 0) { tail.next = curr; tail = curr; curr = curr.next; } head = curr; // Now moving other 0s to end Node prev = curr; curr = curr.next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr.data == 0) { tail.next = curr; tail = curr; prev.next = curr.next; } else prev = curr; // We always move current curr = curr.next; } // Finally making sure that linked // list is null terminated. tail.next = null; return head; } public static Node doubleAndAppend0(Node head) { // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head); } // function to display the nodes public static void display(Node head) { while (head != null) { System.out.print(head.data + " -> "); head = head.next; } } // Driver code public static void main(String[] args) { Node head = new Node(4); head.next = new Node(4); head.next.next = new Node(0); head.next.next.next = new Node(2); head.next.next.next.next = new Node(3); head.next.next.next.next.next = new Node(4); head.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next.next.next.next = new Node(4); System.out.println("Original linked list :"); display(head); head = doubleAndAppend0(head); System.out.println("\nModified linked list :"); display(head); }} |
C++
// C++ code to modify linked list#include <bits/stdc++.h>using namespace std;// Linked List Nodeclass Node {public: int data; Node* next; // Constructorpublic: Node(int dat) { data = dat; next = NULL; }};// Recursive function to double the one of two// elements and make next one as 0,// which are equal before 0void changeTwoBefore0(Node* head){ // there should be atleast three elements // to perform required operation if (head == NULL || head->next == NULL || head->next->next == NULL) return; // when two continuous elements // are same if ((head->data == head->next->data) && (head->next->next->data == 0)) { int temp = head->data; head->data = 2 * temp; head->next->data = 0; if (head->next->next->next != NULL) head = head->next->next->next; else return; } else head = head->next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head);}// function to append zeros at tailNode* appendZero(Node* head){ if (head == NULL || head->next == NULL) return head; // Find tail node Node* tail = head; while (tail->next != NULL) tail = tail->next; Node* origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. Node* curr = head; while (curr->next != NULL && curr->data == 0) { tail->next = curr; tail = curr; curr = curr->next; } head = curr; // Now moving other 0s to end Node* prev = curr; curr = curr->next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr->data == 0) { tail->next = curr; tail = curr; prev->next = curr->next; } else prev = curr; // We always move current curr = curr->next; } // Finally making sure that linked // list is NULL terminated. tail->next = NULL; return head;}Node* doubleAndAppend0(Node* head){ // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head);}// function to display the nodesvoid display(Node* head){ while (head != NULL) { cout << head->data << " -> "; head = head->next; }}// Driver Codeint main(){ Node* head = new Node(4); head->next = new Node(4); head->next->next = new Node(0); head->next->next->next = new Node(2); head->next->next->next->next = new Node(3); head->next->next->next->next->next = new Node(4); head->next->next->next->next->next->next = new Node(3); head->next->next->next->next->next->next->next = new Node(3); head->next->next->next->next->next->next->next->next = new Node(0); head->next->next->next->next->next->next->next->next ->next = new Node(4); cout << "Original linked list :"; display(head); head = doubleAndAppend0(head); cout << "\nModified linked list :"; display(head); return 0;}// contributed by ajaykr00kj |
Python3
# Python3 code to modify linked list# Linked List Nodeclass Node: # Constructor def __init__(self, data): self.data = data self.next = None # Recursive function to double the one of two# elements and make next one as 0,# which are equal before 0def changeTwoBefore0 (head): # there should be atleast three elements # to perform required operation if (head == None or head.next == None or head.next.next == None): return # when two continuous elements # are same if ((head.data == head.next.data) and (head.next.next.data == 0)): temp = head.data head.data = 2*temp head.next.data = 0 if (head.next.next.next != None): head = head.next.next.next else: return else: head = head.next # recursive call to changeTwoBefore0 # for next element changeTwoBefore0(head) # function to append zeros at taildef appendZero( head): if (head == None or head.next == None): return head # Find tail node tail = head while (tail.next != None): tail = tail.next origTail = tail # Case when starting nodes have 0 values # we need to change head in this case. curr = head while (curr.next != None and curr.data == 0): tail.next = curr tail = curr curr = curr.next head = curr # Now moving other 0s to end prev = curr curr = curr.next # We check until original tail while (curr != origTail): # If current data is 0, append # after tail and update tail. if (curr.data == 0): tail.next = curr tail = curr prev.next = curr.next else: prev = curr # We always move current curr = curr.next # Finally making sure that linked # list is None terminated. tail.next = None return head def doubleAndAppend0(head): # Change two same nodes before 0 changeTwoBefore0(head) # Move all 0s to end return appendZero(head) # function to display the nodesdef display( head): while (head != None): print(head.data ,end = " -> ") head = head.next# Driver codehead = Node(4)head.next = Node(4)head.next.next = Node(0)head.next.next.next = Node(2)head.next.next.next.next = Node(3)head.next.next.next.next.next = Node(4)head.next.next.next.next.next.next = Node(3)head.next.next.next.next.next.next.next = Node(3)head.next.next.next.next.next.next.next.next = Node(0)head.next.next.next.next.next.next.next.next.next = Node(4)print("Original linked list :")display(head) head = doubleAndAppend0(head)print("\nModified linked list :")display(head) # This code is contributed by Arnab Kundu |
C#
// C# code to modify linked list using System;// Linked List Node public class Node { public int data; public Node next; // Constructor public Node(int data) { this.data = data; next = null; } } // Class to perform operations // on linked list public class GfG { // Recursive function to double the one of two // elements and make next one as 0, // which are equal before 0 public static void changeTwoBefore0(Node head) { // there should be atleast three elements // to perform required operation if (head == null || head.next == null || head.next.next == null) return; // when two continuous elements // are same if ((head.data == head.next.data) && (head.next.next.data == 0)) { int temp = head.data; head.data = 2*temp; head.next.data = 0; if (head.next.next.next != null) head = head.next.next.next; else return; } else head = head.next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head); } // function to append zeros at tail public static Node appendZero(Node head) { if (head == null || head.next == null) return head; // Find tail node Node tail = head; while (tail.next != null) tail = tail.next; Node origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. Node curr = head; while (curr.next != null && curr.data == 0) { tail.next = curr; tail = curr; curr = curr.next; } head = curr; // Now moving other 0s to end Node prev = curr; curr = curr.next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr.data == 0) { tail.next = curr; tail = curr; prev.next = curr.next; } else prev = curr; // We always move current curr = curr.next; } // Finally making sure that linked // list is null terminated. tail.next = null; return head; } public static Node doubleAndAppend0(Node head) { // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head); } // function to display the nodes public static void display(Node head) { while (head != null) { Console.Write(head.data + " -> "); head = head.next; } } // Driver code public static void Main() { Node head = new Node(4); head.next = new Node(4); head.next.next = new Node(0); head.next.next.next = new Node(2); head.next.next.next.next = new Node(3); head.next.next.next.next.next = new Node(4); head.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next.next.next.next = new Node(4); Console.Write("Original linked list :\n"); display(head); head = doubleAndAppend0(head); Console.WriteLine("\nModified linked list :"); display(head); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// JavaScript code to modify linked list // Linked List Node class Node { constructor(data) { this.data = data; this.next = null; }} // Class to perform operations // on linked list // Recursive function to double the one of two // elements and make next one as 0, // which are equal before 0 function changeTwoBefore0(head) { // there should be atleast three elements // to perform required operation if (head == null || head.next == null || head.next.next == null) return; // when two continuous elements // are same if ((head.data == head.next.data) && (head.next.next.data == 0)) { var temp = head.data; head.data = 2*temp; head.next.data = 0; if (head.next.next.next != null) head = head.next.next.next; else return; } else head = head.next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head); } // function to append zeros at tail function appendZero(head) { if (head == null || head.next == null) return head; // Find tail node var tail = head; while (tail.next != null) tail = tail.next; var origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. var curr = head; while (curr.next != null && curr.data == 0) { tail.next = curr; tail = curr; curr = curr.next; } head = curr; // Now moving other 0s to end var prev = curr; curr = curr.next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr.data == 0) { tail.next = curr; tail = curr; prev.next = curr.next; } else prev = curr; // We always move current curr = curr.next; } // Finally making sure that linked // list is null terminated. tail.next = null; return head; } function doubleAndAppend0(head) { // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head); } // function to display the nodes function display( head) { while (head != null) { document.write(head.data + " -> "); head = head.next; } } // Driver code var head = new Node(4); head.next = new Node(4); head.next.next = new Node(0); head.next.next.next = new Node(2); head.next.next.next.next = new Node(3); head.next.next.next.next.next = new Node(4); head.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next.next.next.next = new Node(4); document.write("Original linked list :<br>"); display(head); head = doubleAndAppend0(head); document.write("<br>Modified linked list :<br>"); display(head); </script> |
Output
Original linked list : 4 -> 4 -> 0 -> 2 -> 3 -> 4 -> 3 -> 3 -> 0 -> 4 -> Modified linked list : 8 -> 2 -> 3 -> 4 -> 6 -> 4 -> 0 -> 0 -> 0 -> 0 ->
Time complexity: O(n), where n is the number of nodes of linked list.
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!
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/double-elements-and-append-zeros-in-linked-list/ […]