Double a Number Represented as a Linked List — LeetCode 2816 Python Solution
MediumStackLinked ListMath
- Problem
- #2816
- Pattern
- Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
Python
# 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)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(1) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2816. Double a Number Represented as a Linked List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2816. Double a Number Represented as a Linked List?
- LeetCode 2816. Double a Number Represented as a Linked List is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2816. Double a Number Represented as a Linked List?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2816. Double a Number Represented as a Linked List?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2816. Double a Number Represented as a Linked List cover?
- LeetCode 2816. Double a Number Represented as a Linked List is tagged Stack, Linked List and Math on LeetCode.