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)$.
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcdoubleIt(head*ListNode)*ListNode{head=reverse(head)dummy:=&ListNode{}cur:=dummymul,carry:=2,0forhead!=nil{x:=head.Val*mul+carrycarry=x/10cur.Next=&ListNode{Val:x%10}cur=cur.Nexthead=head.Next}ifcarry>0{cur.Next=&ListNode{Val:carry}}returnreverse(dummy.Next)}funcreverse(head*ListNode)*ListNode{dummy:=&ListNode{}cur:=headforcur!=nil{next:=cur.Nextcur.Next=dummy.Nextdummy.Next=curcur=next}returndummy.Next}