Add One to Linked List Editorial

Practice Problem Link: Add One to Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a natural number in the form of a linked list, add 1 to it.

Approach

The idea is to go to the last node recursively and add 1 to it. Now keep a track of the carry while traversing from the last node to the first node and update the node values accordingly. If the value of carry is 1 after the traversal then add a new head node with value 1.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n), considering the recursive stack.

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
int addOne(ListNode* head) {
	if (head == NULL) {
		return 1;
	}
	int carry = addOne(head->next);
	int sum = head->data + carry;
	head->data = sum % 10;
	carry = sum / 10;
	return carry;
}
ListNode* addOneToList(ListNode* head) {
	int carry = addOne(head);
	if (carry == 1) {
		ListNode* temp = new ListNode(carry);
		temp->next = head;
		head = temp;
	}
	return head;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	int addOne(ListNode head) {
		if (head == null) {
			return 1;
		}
		int carry = addOne(head.next);
		int sum = head.data + carry;
		head.data = sum % 10;
		carry = sum / 10;
		return carry;
	}
	ListNode addOneToList(ListNode head) {
		int carry = addOne(head);
		if (carry == 1) {
			ListNode temp = new ListNode(carry);
			temp.next = head;
			head = temp;
		}
		return head;
	}
}

Another Approach

• Reverse the given linked list. 
• Add 1 to the new head and traverse the linked list. 
• If there is carry at any node then assign carry as 1 and add it to the next node. 
• Again reverse the modified list and return its head.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* reverseLinkedList (ListNode* head) {
	ListNode* previous = NULL;
	ListNode* current = head;
	ListNode* next;
	while (current != NULL) {
		next = current->next;
		current->next = previous;
		previous = current;
		current = next;
	}
	return previous;
}
ListNode* addOneToList(ListNode* head) {
	head = reverseLinkedList(head);
	ListNode* currNode = head;
	ListNode* prev = NULL;
	int carry = 1;
	while (currNode != NULL) {
		currNode->data = currNode->data + carry;
		carry = (currNode->data) / 10;
		currNode->data = (currNode->data) % 10;
		prev = currNode;
		currNode = currNode->next;
	}
	if (carry != 0) {
		ListNode* newNode = new ListNode(carry);
		prev->next = newNode;
	}
	return reverseLinkedList(head);
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode reverseLinkedList (ListNode head) {
		ListNode previous = null;
		ListNode current = head;
		ListNode next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		return previous;
	}
	
	ListNode addOneToList(ListNode head) {
		head = reverseLinkedList(head);
		ListNode currNode = head;
		ListNode prev = null;
		int carry = 1;
		while (currNode != null) {
			currNode.data = currNode.data + carry;
			carry = (currNode.data) / 10;
			currNode.data = (currNode.data) % 10;
			prev = currNode;
			currNode = currNode.next;
		}
		if (carry != 0) {
			ListNode newNode = new ListNode(carry);
			prev.next = newNode;
		}

		return reverseLinkedList(head);
	}
}