Number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1-> 9-> 9 -> 9) and adding 1 to it should change it to (2->0->0->0)
Below are the steps :
- Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.
- Start traversing linked list from leftmost node and add 1 to it. If there is a carry, move to the next node. Keep moving to the next node while there is a carry.
- Reverse modified linked list and return head.
Below is the implementation of above steps.
Javascript
<script>// Javascript program to add 1 to // a linked list // Linked list node class Node { constructor() { this.data = 0; this.next = null; }}; /* Function to create a new node with given data */function newNode(data) { var new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } // Function to reverse the // linked list function reverse(head) { var prev = null; var current = head; var next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } return prev; } /* Adds one to a linked lists and return the head node of resultant list */function addOneUtil(head) { // res is head node of the // resultant list var res = head; var temp, prev = null; var carry = 1, sum; // while both lists exist while (head != null) { // Calculate value of next digit in // resultant list. The next digit is // sum of following things // (i) Carry // (ii) Next digit of head list (if // there is a next digit) sum = carry + head.data; // update carry for next calculation carry = (sum >= 10)? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data head.data = sum; // Move head and second pointers to // next nodes temp = head; head = head.next; } // if some carry is still there, add a // new node to result list. if (carry > 0) temp.next = newNode(carry); // return head of the resultant list return res; } // This function mainly uses addOneUtil(). function addOne(head) { // Reverse linked list head = reverse(head); // Add one from left to right of // reversed list head = addOneUtil(head); // Reverse the modified list return reverse(head); } // A utility function to print a // linked list function printList(node) { while (node != null) { document.write(node.data); node = node.next; } document.write("<br>");} // Driver codevar head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); document.write( "List is "); printList(head); head = addOne(head); document.write("<br>Resultant list is "); printList(head); // This code is contributed by rrrtnx.</script> |
Output:
List is 1999 Resultant list is 2000
Time Complexity: O(n)
Auxiliary Space: O(1)
Recursive Implementation:
We can recursively reach the last node and forward carry to previous nodes. Recursive solution doesn’t require reversing of linked list. We can also use a stack in place of recursion to temporarily hold nodes.
Below is the implementation of recursive solution.
Javascript
<script>// Recursive JavaScript program// to add 1 to a linked list// Linked list node class Node{ constructor() { this.data = 0; this.next = null; }}/* Function to create a new node with given data */function newNode(data) { var new_node = new Node(); new_node.data = data; new_node.next = null; return new_node;}// Recursively add 1 from end to // beginning and returns carry after // all nodes are processed.function addWithCarry(head) { // If linked list is empty, then // return carry if (head == null) return 1; // Add carry returned be next node // call var res = head.data + addWithCarry(head.next); // Update data and return new carry head.data = res % 10; return parseInt(res / 10);}// This function mainly uses // addWithCarry().function addOne(head) { // Add 1 to linked list from end // to beginning var carry = addWithCarry(head); var newNodes = null; // If there is carry after processing // all nodes, then we need to add a // new node to linked list if (carry > 0) { newNodes = newNode(carry); newNodes.next = head; // New node becomes head now return newNodes; } return head;}// A utility function to print a // linked listfunction printList(node) { while (node != null) { document.write(node.data); node = node.next; } document.write("<br>");}// Driver code var head = newNode(1);head.next = newNode(9);head.next.next = newNode(9);head.next.next.next = newNode(9);document.write("List is ");printList(head);head = addOne(head);document.write("<br>");document.write("Resultant list is ");printList(head);</script> |
Output:
List is 1999 Resultant list is 2000
Please refer complete article on Add 1 to a number represented as linked list for more details!
Share your thoughts in the comments
