Given a singly linked list, with some positive numbers (valid numbers) and zeros (invalid numbers). Convert the linked list in such a way that if next valid number is same as current number, double its value and replace the next number with 0. After the modification, rearrange the linked list such that all 0’s are shifted to the end.
Examples:
Input : 2->2->0->4->0->8 Output : 4->4->8->0->0->0 Input : 0->2->2->2->0->6->6->0->0->8 Output : 4->2->12->8->0->0->0->0->0->0
Source: Microsoft IDC Interview Experience | Set 156.
Approach: First modify the linked list as mentioned, i.e., if next valid number is same as current number, double its value and replace the next number with 0.
Algorithm for Modification:
1. ptr = head 2. while (ptr && ptr->next) 3. if (ptr->data == 0) || (ptr->data != ptr->next->data) 4. ptr = ptr->next 5. else 6. ptr->data = 2 * ptr->data 7. ptr->next->data = 0 8. ptr = ptr->next->next
After modifying the list segregate the valid (non-zero) and invalid (zero) elements. It is same as Segregating Even and Odd nodes in a Linked list.
Implementation:
C++
// C++ implementation to modify and // rearrange list #include <bits/stdc++.h> using namespace std; // structure of a node struct Node { int data; Node* next; }; // function to get a new node Node* getNode( int data) { // allocate space Node* newNode = (Node*) malloc ( sizeof (Node)); // put in the data newNode->data = data; newNode->next = NULL; return newNode; } // function to segregate valid (non-zero) numbers and // invalid (zero) numbers in a list Node* segValidInvalidNum(Node* head) { // valid (non-zero numbers) list start and // end pointers Node *validStart = NULL, *validEnd = NULL; // invalid (zero numbers) list start and // end pointers Node *invalidStart = NULL, *invalidEnd = NULL; Node* currentNode = head; // traverse the given list while (currentNode != NULL) { // current node's data int element = currentNode->data; // if it is a non-zero element, then // add it to valid list if (element != 0) { if (validStart == NULL) { validStart = currentNode; validEnd = validStart; } else { validEnd->next = currentNode; validEnd = validEnd->next; } } // else it is a zero element, so // add it to invalid list else { if (invalidStart == NULL) { invalidStart = currentNode; invalidEnd = invalidStart; } else { invalidEnd->next = currentNode; invalidEnd = invalidEnd->next; } } // Move to the next node currentNode = currentNode->next; } // if true then return the original list as it is if (validStart == NULL || invalidStart == NULL) return head; // add the invalid list to the end of valid list validEnd->next = invalidStart; invalidEnd->next = NULL; head = validStart; // required head of the new list return head; } // function to modify and // rearrange list Node* modifyAndRearrangeList(Node* head) { // if list is empty or contains a single // element only if (head == NULL || head->next == NULL) return head; // traverse the list Node* ptr = head; while (ptr && ptr->next) { // if current node's data is '0' or it is not equal // to next nodes data, them move one node ahead if ((ptr->data == 0) || (ptr->data != ptr->next->data)) ptr = ptr->next; else { // double current node's data ptr->data = 2 * ptr->data; // put '0' in next node's data ptr->next->data = 0; // move two nodes ahead ptr = ptr->next->next; } } // segregate valid (non-zero) and // invalid (non-zero) numbers return segValidInvalidNum(head); } // function to print a linked list void printList(Node* head) { while (head != NULL) { cout << head->data << " " ; head = head->next; } } // Driver program to test above int main() { Node* head = getNode(2); head->next = getNode(2); head->next->next = getNode(0); head->next->next->next = getNode(4); head->next->next->next->next = getNode(0); head->next->next->next->next->next = getNode(8); cout << "Original List: " ; printList(head); head = modifyAndRearrangeList(head); cout << "\nModified List: " ; printList(head); return 0; } |
Java
// Java implementation to modify and // rearrange list class GFG { // structure of a node static class Node { int data; Node next; }; // function to get a new node static Node getNode( int data) { // allocate space Node newNode = new Node(); // put in the data newNode.data = data; newNode.next = null ; return newNode; } // function to segregate valid (non-zero) numbers // and invalid (zero) numbers in a list static Node segValidInvalidNum(Node head) { // valid (non-zero numbers) list start // and end pointers Node validStart = null , validEnd = null ; // invalid (zero numbers) list start and // end pointers Node invalidStart = null , invalidEnd = null ; Node currentNode = head; // traverse the given list while (currentNode != null ) { // current node's data int element = currentNode.data; // if it is a non-zero element, then // add it to valid list if (element != 0 ) { if (validStart == null ) { validStart = currentNode; validEnd = validStart; } else { validEnd.next = currentNode; validEnd = validEnd.next; } } // else it is a zero element, so // add it to invalid list else { if (invalidStart == null ) { invalidStart = currentNode; invalidEnd = invalidStart; } else { invalidEnd.next = currentNode; invalidEnd = invalidEnd.next; } } // Move to the next node currentNode = currentNode.next; } // if true then return the original list as it is if (validStart == null || invalidStart == null ) return head; // add the invalid list to the end of valid list validEnd.next = invalidStart; invalidEnd.next = null ; head = validStart; // required head of the new list return head; } // function to modify and // rearrange list static Node modifyAndRearrangeList(Node head) { // if list is empty or contains a single // element only if (head == null || head.next == null ) return head; // traverse the list Node ptr = head; while (ptr != null && ptr.next != null ) { // if current node's data is '0' or // it is not equal to next nodes data, // them move one node ahead if ((ptr.data == 0 ) || (ptr.data != ptr.next.data)) ptr = ptr.next; else { // double current node's data ptr.data = 2 * ptr.data; // put '0' in next node's data ptr.next.data = 0 ; // move two nodes ahead ptr = ptr.next.next; } } // segregate valid (non-zero) and // invalid (non-zero) numbers return segValidInvalidNum(head); } // function to print a linked list static void printList(Node head) { while (head != null ) { System.out.print(head.data + " " ); head = head.next; } } // Driver Code public static void main(String[] args) { Node head = getNode( 2 ); head.next = getNode( 2 ); head.next.next = getNode( 0 ); head.next.next.next = getNode( 4 ); head.next.next.next.next = getNode( 0 ); head.next.next.next.next.next = getNode( 8 ); System.out.print( "Original List: " ); printList(head); head = modifyAndRearrangeList(head); System.out.print( "\nModified List: " ); printList(head); } } // This code is contributed by Rajput-Ji |
Python
# Python implementation to modify and # rearrange list # structure of a node class Node: def __init__( self , data): self .data = data self . next = None # function to get a new node def getNode( data) : # allocate space newNode = Node( 0 ) # put in the data newNode.data = data newNode. next = None return newNode # function to segregate valid (non-zero) numbers # and invalid (zero) numbers in a list def segValidInvalidNum(head) : # valid (non-zero numbers) list start # and end pointers validStart = None validEnd = None # invalid (zero numbers) list start and # end pointers invalidStart = None invalidEnd = None currentNode = head # traverse the given list while (currentNode ! = None ) : # current node's data element = currentNode.data # if it is a non-zero element, then # add it to valid list if (element ! = 0 ): if (validStart = = None ): validStart = currentNode validEnd = validStart else : validEnd. next = currentNode validEnd = validEnd. next # else it is a zero element, so # add it to invalid list else : if (invalidStart = = None ): invalidStart = currentNode invalidEnd = invalidStart else : invalidEnd. next = currentNode invalidEnd = invalidEnd. next # Move to the next node currentNode = currentNode. next # if true then return the original list as it is if (validStart = = None or invalidStart = = None ): return head # add the invalid list to the end of valid list validEnd. next = invalidStart invalidEnd. next = None head = validStart # required head of the new list return head # function to modify and # rearrange list def modifyAndRearrangeList( head) : # if list is empty or contains a single # element only if (head = = None or head. next = = None ): return head # traverse the list ptr = head while (ptr ! = None and ptr. next ! = None ) : # if current node's data is '0' or # it is not equal to next nodes data, # them move one node ahead if ((ptr.data = = 0 ) or (ptr.data ! = ptr. next .data)) : ptr = ptr. next else : # double current node's data ptr.data = 2 * ptr.data # put '0' in next node's data ptr. next .data = 0 # move two nodes ahead ptr = ptr. next . next # segregate valid (non-zero) and # invalid (non-zero) numbers return segValidInvalidNum(head) # function to print a linked list def printList( head) : while (head ! = None ): print (head.data, end = " " ) head = head. next # Driver Code head = getNode( 2 ) head. next = getNode( 2 ) head. next . next = getNode( 0 ) head. next . next . next = getNode( 4 ) head. next . next . next . next = getNode( 0 ) head. next . next . next . next . next = getNode( 8 ) print ( "Original List: " ) printList(head) head = modifyAndRearrangeList(head) print ( "\nModified List: " ) printList(head) # This code is contributed by Arnab Kundu |
C#
// C# implementation to modify and // rearrange list using System; class GFG { // structure of a node public class Node { public int data; public Node next; }; // function to get a new node static Node getNode( int data) { // allocate space Node newNode = new Node(); // put in the data newNode.data = data; newNode.next = null ; return newNode; } // function to segregate valid (non-zero) numbers // and invalid (zero) numbers in a list static Node segValidInvalidNum(Node head) { // valid (non-zero numbers) list // start and end pointers Node validStart = null , validEnd = null ; // invalid (zero numbers) list start and // end pointers Node invalidStart = null , invalidEnd = null ; Node currentNode = head; // traverse the given list while (currentNode != null ) { // current node's data int element = currentNode.data; // if it is a non-zero element, // then add it to valid list if (element != 0) { if (validStart == null ) { validStart = currentNode; validEnd = validStart; } else { validEnd.next = currentNode; validEnd = validEnd.next; } } // else it is a zero element, // so add it to invalid list else { if (invalidStart == null ) { invalidStart = currentNode; invalidEnd = invalidStart; } else { invalidEnd.next = currentNode; invalidEnd = invalidEnd.next; } } // Move to the next node currentNode = currentNode.next; } // if true then return the // original list as it is if (validStart == null || invalidStart == null ) return head; // add the invalid list to // the end of valid list validEnd.next = invalidStart; invalidEnd.next = null ; head = validStart; // required head of the new list return head; } // function to modify and // rearrange list static Node modifyAndRearrangeList(Node head) { // if list is empty or contains // a single element only if (head == null || head.next == null ) return head; // traverse the list Node ptr = head; while (ptr != null && ptr.next != null ) { // if current node's data is '0' or // it is not equal to next nodes data, // them move one node ahead if ((ptr.data == 0) || (ptr.data != ptr.next.data)) ptr = ptr.next; else { // double current node's data ptr.data = 2 * ptr.data; // put '0' in next node's data ptr.next.data = 0; // move two nodes ahead ptr = ptr.next.next; } } // segregate valid (non-zero) and // invalid (non-zero) numbers return segValidInvalidNum(head); } // function to print a linked list static void printList(Node head) { while (head != null ) { Console.Write(head.data + " " ); head = head.next; } } // Driver Code public static void Main(String[] args) { Node head = getNode(2); head.next = getNode(2); head.next.next = getNode(0); head.next.next.next = getNode(4); head.next.next.next.next = getNode(0); head.next.next.next.next.next = getNode(8); Console.Write( "Original List: " ); printList(head); head = modifyAndRearrangeList(head); Console.Write( "\nModified List: " ); printList(head); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation to modify and // rearrange list // structure of a node class Node { constructor() { this .data = 0; this .next = null ; } } // function to get a new node function getNode(data) { // allocate space var newNode = new Node(); // put in the data newNode.data = data; newNode.next = null ; return newNode; } // function to segregate valid (non-zero) numbers // and invalid (zero) numbers in a list function segValidInvalidNum(head) { // valid (non-zero numbers) list // start and end pointers var validStart = null , validEnd = null ; // invalid (zero numbers) list start and // end pointers var invalidStart = null , invalidEnd = null ; var currentNode = head; // traverse the given list while (currentNode != null ) { // current node's data var element = currentNode.data; // if it is a non-zero element, // then add it to valid list if (element != 0) { if (validStart == null ) { validStart = currentNode; validEnd = validStart; } else { validEnd.next = currentNode; validEnd = validEnd.next; } } // else it is a zero element, // so add it to invalid list else { if (invalidStart == null ) { invalidStart = currentNode; invalidEnd = invalidStart; } else { invalidEnd.next = currentNode; invalidEnd = invalidEnd.next; } } // Move to the next node currentNode = currentNode.next; } // if true then return the // original list as it is if (validStart == null || invalidStart == null ) return head; // add the invalid list to // the end of valid list validEnd.next = invalidStart; invalidEnd.next = null ; head = validStart; // required head of the new list return head; } // function to modify and // rearrange list function modifyAndRearrangeList(head) { // if list is empty or contains // a single element only if (head == null || head.next == null ) return head; // traverse the list var ptr = head; while (ptr != null && ptr.next != null ) { // if current node's data is '0' or // it is not equal to next nodes data, // them move one node ahead if (ptr.data == 0 || ptr.data != ptr.next.data) ptr = ptr.next; else { // double current node's data ptr.data = 2 * ptr.data; // put '0' in next node's data ptr.next.data = 0; // move two nodes ahead ptr = ptr.next.next; } } // segregate valid (non-zero) and // invalid (non-zero) numbers return segValidInvalidNum(head); } // function to print a linked list function printList(head) { while (head != null ) { document.write(head.data + " " ); head = head.next; } } // Driver Code var head = getNode(2); head.next = getNode(2); head.next.next = getNode(0); head.next.next.next = getNode(4); head.next.next.next.next = getNode(0); head.next.next.next.next.next = getNode(8); document.write( "Original List: " ); printList(head); head = modifyAndRearrangeList(head); document.write( "<br>Modified List: " ); printList(head); // This code is contributed by rdtank. </script> |
Original List: 2 2 0 4 0 8 Modified List: 4 4 8 0 0 0
Time Complexity: O(n).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!