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.
Java
// Java program to add 1 to a // linked listclass GfG { // Linked list node static class Node { int data; Node next; } /* Function to create a new node with given data */ static Node newNode(int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } // Function to reverse the linked list static Node reverse(Node head) { Node prev = null; Node current = head; Node next = null; 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 */ static Node addOneUtil(Node head) { // res is head node of the // resultant list Node res = head; Node temp = null, prev = null; int 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(). static Node addOne(Node 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 static void printList(Node node) { while (node != null) { System.out.print(node.data); node = node.next; } System.out.println(); } // Driver code public static void main(String[] args) { Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); System.out.print("List is "); printList(head); head = addOne(head); System.out.println(); System.out.print( "Resultant list is "); printList(head); }}// This code is contributed by prerna saini |
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.
Java
// Recursive Java program to add 1 // to a linked listclass GfG { // Linked list node static class Node { int data; Node next; } /* Function to create a new node with given data */ static Node newNode(int data) { Node 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. static int addWithCarry(Node head) { // If linked list is empty, then // return carry if (head == null) return 1; // Add carry returned be next node // call int res = head.data + addWithCarry(head.next); // Update data and return // new carry head.data = (res) % 10; return (res) / 10; } // This function mainly uses // addWithCarry(). static Node addOne(Node head) { // Add 1 to linked list from end // to beginning int carry = addWithCarry(head); // If there is carry after processing // all nodes, then we need to add a // new node to linked list if (carry > 0) { Node newNode = newNode(carry); newNode.next = head; // New node becomes head now return newNode; } return head; } // A utility function to print a // linked list static void printList(Node node) { while (node != null) { System.out.print(node.data); node = node.next; } System.out.println(); } // Driver code public static void main(String[] args) { Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); System.out.print("List is "); printList(head); head = addOne(head); System.out.println(); System.out.print("Resultant list is "); printList(head); }}// This code is contributed by shubham96301 |
Output:
List is 1999 Resultant list is 2000
Simple approach and easy implementation: The idea is to store the last non 9 digit pointer so that if the last pointer is zero we can replace all the nodes after stored node(which contains the location of last digit before 9) to 0 and add the value of the stored node by 1
Java
// Recursive Java program to add 1 to // a linked listclass GFG{// Linked list nodestatic class Node{ int data; Node next;}// Function to create a new node // with given datastatic Node newNode(int data){ Node new_node = new Node(); new_node.data = data; new_node.next = null; return new_node;}static Node addOne(Node head){ // Return head of list after // adding one Node ln = head; if (head.next == null) { head.data += 1; return head; } Node t = head; int prev; while (t.next != null) { if (t.data != 9) { ln = t; } t = t.next; } if (t.data == 9 && ln != null) { t = ln; t.data += 1; t = t.next; while (t != null) { t.data = 0; t = t.next; } } else { t.data += 1; } return head;}// A utility function to print // a linked liststatic void printList(Node node){ while (node != null) { System.out.print(node.data); node = node.next; } System.out.println();}// Driver code public static void main(String[] args){ Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); System.out.print("List is "); printList(head); head = addOne(head); System.out.println(); System.out.print("Resultant list is "); printList(head);}}// This code is contributed by rajsanghavi9. |
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!
Feeling lost in the vast world of Backend Development? It’s time for a change! Join our Java Backend Development – Live Course and embark on an exciting journey to master backend development efficiently and on schedule.
What We Offer:
- Comprehensive Course
- Expert Guidance for Efficient Learning
- Hands-on Experience with Real-world Projects
- Proven Track Record with 100,000+ Successful Geeks
Share your thoughts in the comments
