Double a Number Represented as a Linked List

Problem

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

Examples

Example 1:

---
title: Input
---
graph LR;
1 --> 8 --> 9
  

---
title: Output
---
graph LR;
3 --> 7 --> 8
  

Input: head = [1,8,9]
Output: [3,7,8]
Explanation: The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Example 2:

---
title: Input
---
graph LR;
A(9) --> B(9) --> C(9)
  

---
title: Output
---
graph LR;
1 --> A(9) --> B(9) --> 8
  

Input: head = [9,9,9]
Output: [1,9,9,8]
Explanation: The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998. 

Solution

We can double the number in the list, but we have to handle the case where we get carry over from next digit.

Method 1 - Reverse the linked list

Algorithm

1. We can reverse the linked list using Reverse Linked List Problem solution.
2. Now multiply all node’s val by 2, and keep track of carry. We will get carry, when number is 5 or more than 5.
   1. If we see carry, we add 1 to next node, as that is the carry we get. If it 0, we just continue.
   2. Also, remember there is 1 edge case, if last digit is more than equal to 5, we have to create a new node for the last carry.
3. Once we are done with doubling, using step 2, we reverse the list again, to get the right number.

Dry Run

Suppose, the input list is 1->8->9.

1. We reverse the list and get 9->8->1
2. Traverse the list and double the node values and carry values forward. Now, the list is 8->7->3

3. Reverse the list again, and we get 3->7->8

Code

Java

public ListNode doubleIt(ListNode head) {
	ListNode reversed = reverseList(head);

	ListNode curr = reversed;
	int carry = 0;
	
	while (curr != null) {
		int doubledValue = curr.val * 2 + carry;
		curr.val = doubledValue % 10;
		carry = doubledValue / 10;
		curr = curr.next;
	}
	if (carry > 0) {
		curr.next = new ListNode(carry);
	}

	ListNode ans = reverseList(reversed);

	return ans;
}

Complexity

• ⏰ Time complexity: O(n). 3 pass (Reverse + Iterate + Reverse)
• 🧺 Space complexity: O(1) , provided reverse list doesn’t use new pointers.

Method 2 - Iteratively using next val

As, we saw in previous method, we get the carry when the value is more than equal to 5 i.e. more than 4, so number in range [5,9] generate carry. So, we can check value of next node, and see if it is more than 4, if yes, we will add carry to current node.Also, if head node’s value is more than 4, we can create a new node, and make it new node.

Algorithm

1. If the value of the head node is greater than 4 (indicating a carry), prepend a new node with value 0 to the list.
2. Traverse the linked list and double each digit.
   1. If a node’s value is greater than 4 and it has a next node, increment the next node’s value by 1.
3. Return the head of the modified linked list.

Code

Java

public ListNode doubleIt(ListNode head) {
	if (head.val > 4) {
		head = new ListNode(0, head);
	}
	ListNode curr = head;
	while (curr != null) {
		curr.val = (curr.val * 2) % 10;
		if (curr.next != null && curr.next.val > 4) {
			curr.val += 1;
		}
		curr = curr.next;
	}
	return head;
}

Complexity

• ⏰ Time complexity: O(n) - Iterate on list
• 🧺 Space complexity: O(1)