# 2816. Double a Number Represented as a Linked List

## Description

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.

Example 1:

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:

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.


Constraints:

• The number of nodes in the list is in the range [1, 104]
• 0 <= Node.val <= 9
• The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

## Solutions

Solution 1: Reverse Linked List + Simulation

First, we reverse the linked list, then simulate the multiplication operation, and finally reverse the linked list back.

Time complexity is $O(n)$, where $n$ is the length of the linked list. Ignoring the space taken by the answer linked list, the space complexity is $O(1)$.

• /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
ListNode dummy = new ListNode();
ListNode cur = dummy;
int mul = 2, carry = 0;
int x = head.val * mul + carry;
carry = x / 10;
cur.next = new ListNode(x % 10);
cur = cur.next;
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return reverse(dummy.next);
}

ListNode dummy = new ListNode();
while (cur != null) {
ListNode next = cur.next;
cur.next = dummy.next;
dummy.next = cur;
cur = next;
}
return dummy.next;
}
}

• /**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* dummy = new ListNode();
ListNode* cur = dummy;
int mul = 2, carry = 0;
int x = head->val * mul + carry;
carry = x / 10;
cur->next = new ListNode(x % 10);
cur = cur->next;
}
if (carry) {
cur->next = new ListNode(carry);
}
return reverse(dummy->next);
}

ListNode* dummy = new ListNode();
while (cur) {
ListNode* next = cur->next;
cur->next = dummy->next;
dummy->next = cur;
cur = next;
}
return dummy->next;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
while cur:
next = cur.next
cur.next = dummy.next
dummy.next = cur
cur = next
return dummy.next

dummy = cur = ListNode()
mul, carry = 2, 0
x = head.val * mul + carry
carry = x // 10
cur.next = ListNode(x % 10)
cur = cur.next
if carry:
cur.next = ListNode(carry)
return reverse(dummy.next)


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
dummy := &ListNode{}
cur := dummy
mul, carry := 2, 0
carry = x / 10
cur.Next = &ListNode{Val: x % 10}
cur = cur.Next
}
if carry > 0 {
cur.Next = &ListNode{Val: carry}
}
return reverse(dummy.Next)
}

dummy := &ListNode{}
for cur != nil {
next := cur.Next
cur.Next = dummy.Next
dummy.Next = cur
cur = next
}
return dummy.Next
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function doubleIt(head: ListNode | null): ListNode | null {
const dummy = new ListNode();
let cur = dummy;
let mul = 2;
let carry = 0;
const x = head.val * mul + carry;
carry = Math.floor(x / 10);
cur.next = new ListNode(x % 10);
cur = cur.next;
}
if (carry) {
cur.next = new ListNode(carry);
}
return reverse(dummy.next);
}

function reverse(head: ListNode | null): ListNode | null {
const dummy = new ListNode();
while (cur) {
const next = cur.next;
cur.next = dummy.next;
dummy.next = cur;
cur = next;
}
return dummy.next;
}