Merge pull request #303 from parmeet9891/master

abranhe · web-flow · commit 765890623f30 · 2020-10-06T16:14:40.000-04:00
Incrementing Linked List by one.
diff --git a/data-structures/IncrementLL.cpp b/data-structures/IncrementLL.cpp
@@ -0,0 +1,127 @@
+#include<bits/stdc++.h>
+using namespace std;
+
+/*
+
+Increment Linked List by 1
+
+This program increments the list by 1. The program takes input with one space and when entered -1 at the end, it stops taking more inputs
+For example
+
+Input:
+3 1 -1
+
+Output:
+3 2
+
+Input2:
+9 9 -1
+
+Output2:
+1 0 0
+
+Idea is to reverse a LL, made some calculations and reverse it again to obtain the answer.
+
+*/
+
+class Node {
+	public:
+		int data;
+		Node *next;
+		
+		Node(int data) {
+			this->data = data;
+			this->next = NULL;
+		}
+};
+
+Node* takeInput() {
+	Node* head = NULL;
+	Node* prev = NULL;
+	int d;
+	cin >> d;
+	
+	while(d != -1) {
+		Node* newnode = new Node(d);
+		if(head == NULL) {
+			head = newnode;
+			prev = head;
+		}
+		else {
+			prev->next = newnode;
+			prev = newnode;
+		}
+		cin >> d;
+	}
+	return head;
+}
+
+Node* reverseLL(Node* head) {
+	Node* curr = head;
+	Node* prev = NULL;
+	while(curr != NULL) {
+		if(prev == NULL) {
+			prev = curr;
+			curr = curr->next;
+			prev->next = NULL;
+		}
+		else {
+			Node* var = curr;
+			curr = curr->next;
+			var->next = prev;
+			prev = var;
+		}
+	}
+	return prev;
+}
+
+void print(Node* head) {
+	Node* temp = head;
+	while(temp != NULL) {
+		cout<<temp->data<<" ";
+		temp = temp->next;
+	}
+}
+
+int main() {
+	Node* head = takeInput();
+	Node *newHead = NULL;
+	newHead = reverseLL(head);
+	
+	bool carry = false;
+	
+	Node *temp = newHead;
+	Node *prev = NULL;
+	int digit = temp->data + 1;
+	while(temp!= NULL) {
+		if(carry) {
+			int data = temp->data + 1;
+			if(data >= 10) {
+				temp->data = (data%10);
+				carry = true;	
+			}
+			else {
+				temp->data = data;
+				carry = false;
+				break;
+			}
+		}
+		else if(digit>=10) {
+			temp->data = (digit%10);
+			carry = true;	
+		}
+		else if(digit<10) {
+			temp->data = temp->data + 1;
+			break;
+		}
+		prev = temp;
+		temp = temp->next;
+	}
+	if(carry) {
+		Node* newNode = new Node(1);
+		prev->next = newNode;
+		newNode->next = NULL;
+	}
+	head = reverseLL(newHead);
+	print(head);
+}
