« Next Number

Given a large number represented in the form of a linked list. Write code to increment the number by 1 in-place(i.e. without using extra space). Note: You don't need to print the elements, just update the elements and return the head of updated LL.

Input Constraints:

1 <= Length of Linked List <=10^6.

Input format :

Line 1 : Linked list elements (separated by space and terminated by -1)

Output Format :

Line 1: Updated linked list elements

Sample Input 1 :

3 9 2 5 -1

Sample Output 1 :

3 9 2 6

Sample Input 2 :

9 9 9 -1

Sample Output 1 :

1 0 0 0

Copy
1#include <iostream>
2using namespace std;
3
4class Node{
5public:
6    int data;
7    Node *next;
8    Node(int data){
9        this -> data = data;
10        this -> next = NULL;
11    }
12};
13
14int NextLargeNumberUtil(Node *head){
15    if(head == NULL){
16        return 1;
17    }
18    int carry = NextLargeNumberUtil(head->next);
19    int x = carry + head->data;
20    if(x >= 10){
21        head->data = x%10;
22        return x/10;
23    }else{
24        head->data = x;
25        return 0;
26    }
27}
28
29Node* NextLargeNumber(Node *head) {
30    int y = NextLargeNumberUtil(head);
31    if(y > 0){
32        Node *newNode = new Node(y);
33        newNode->next = head;
34        head = newNode;
35    }
36    return head;
37
38}
39
40Node* takeinput() {
41    int data;
42    cin >> data;
43    Node* head = NULL, *tail = NULL;
44    while(data != -1){
45        Node *newNode = new Node(data);
46        if(head == NULL)                  {
47            head = newNode;
48            tail = newNode;
49        }
50        else{
51            tail -> next = newNode;
52            tail = newNode;
53        }
54        cin >> data;
55    }
56    return head;
57}
58
59void print(Node *head) {
60    Node *temp = head;
61    while(temp != NULL) {
62        cout << temp -> data << " ";
63        temp = temp -> next;
64    }
65    cout<<endl;
66}
67
68int main() {
69    Node *head = takeinput();
70
71    head = NextLargeNumber(head);
72    print(head);
73    return 0;
74}