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)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| # 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]:
def reverse(head):
dummy = ListNode()
cur = head
while cur:
next = cur.next
cur.next = dummy.next
dummy.next = cur
cur = next
return dummy.next
head = reverse(head)
dummy = cur = ListNode()
mul, carry = 2, 0
while head:
x = head.val * mul + carry
carry = x // 10
cur.next = ListNode(x % 10)
cur = cur.next
head = head.next
if carry:
cur.next = ListNode(carry)
return reverse(dummy.next)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| /**
* Definition for singly-linked list.
* 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 {
public ListNode doubleIt(ListNode head) {
head = reverse(head);
ListNode dummy = new ListNode();
ListNode cur = dummy;
int mul = 2, carry = 0;
while (head != null) {
int x = head.val * mul + carry;
carry = x / 10;
cur.next = new ListNode(x % 10);
cur = cur.next;
head = head.next;
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return reverse(dummy.next);
}
private ListNode reverse(ListNode head) {
ListNode dummy = new ListNode();
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = dummy.next;
dummy.next = cur;
cur = next;
}
return dummy.next;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| /**
* Definition for singly-linked list.
* 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* doubleIt(ListNode* head) {
head = reverse(head);
ListNode* dummy = new ListNode();
ListNode* cur = dummy;
int mul = 2, carry = 0;
while (head) {
int x = head->val * mul + carry;
carry = x / 10;
cur->next = new ListNode(x % 10);
cur = cur->next;
head = head->next;
}
if (carry) {
cur->next = new ListNode(carry);
}
return reverse(dummy->next);
}
ListNode* reverse(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* cur = head;
while (cur) {
ListNode* next = cur->next;
cur->next = dummy->next;
dummy->next = cur;
cur = next;
}
return dummy->next;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func doubleIt(head *ListNode) *ListNode {
head = reverse(head)
dummy := &ListNode{}
cur := dummy
mul, carry := 2, 0
for head != nil {
x := head.Val*mul + carry
carry = x / 10
cur.Next = &ListNode{Val: x % 10}
cur = cur.Next
head = head.Next
}
if carry > 0 {
cur.Next = &ListNode{Val: carry}
}
return reverse(dummy.Next)
}
func reverse(head *ListNode) *ListNode {
dummy := &ListNode{}
cur := head
for cur != nil {
next := cur.Next
cur.Next = dummy.Next
dummy.Next = cur
cur = next
}
return dummy.Next
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| /**
* Definition for singly-linked list.
* 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 {
head = reverse(head);
const dummy = new ListNode();
let cur = dummy;
let mul = 2;
let carry = 0;
while (head) {
const x = head.val * mul + carry;
carry = Math.floor(x / 10);
cur.next = new ListNode(x % 10);
cur = cur.next;
head = head.next;
}
if (carry) {
cur.next = new ListNode(carry);
}
return reverse(dummy.next);
}
function reverse(head: ListNode | null): ListNode | null {
const dummy = new ListNode();
let cur = head;
while (cur) {
const next = cur.next;
cur.next = dummy.next;
dummy.next = cur;
cur = next;
}
return dummy.next;
}
|
