Skip to content

2816. Double a Number Represented as a Linked List 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  ListNode* doubleIt(ListNode* head) {
    if (getCarry(head) == 1)
      return new ListNode(1, head);
    return head;
  }

 private:
  int getCarry(ListNode* node) {
    int val = node->val * 2;
    if (node->next != nullptr)
      val += getCarry(node->next);

    node->val = val % 10;
    return val / 10;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public ListNode doubleIt(ListNode head) {
    if (getCarry(head) == 1)
      return new ListNode(1, head);
    return head;
  }

  private int getCarry(ListNode node) {
    int val = node.val * 2;
    if (node.next != null)
      val += getCarry(node.next);
    node.val = val % 10;
    return val / 10;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def doubleIt(self, head: ListNode | None) -> ListNode | None:
    def getCarry(node: ListNode | None) -> ListNode | None:
      val = node.val * 2
      if node.next:
        val += getCarry(node.next)
      node.val = val % 10
      return val // 10

    if getCarry(head) == 1:
      return ListNode(1, head)
    return head

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  ListNode* doubleIt(ListNode* head) {
    if (head->val >= 5)
      head = new ListNode(0, head);

    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
      curr->val *= 2;
      curr->val %= 10;
      if (curr->next && curr->next->val >= 5)
        ++curr->val;
    }

    return head;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public ListNode doubleIt(ListNode head) {
    if (head.val >= 5)
      head = new ListNode(0, head);

    for (ListNode curr = head; curr != null; curr = curr.next) {
      curr.val *= 2;
      curr.val %= 10;
      if (curr.next != null && curr.next.val >= 5)
        ++curr.val;
    }

    return head;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def doubleIt(self, head: ListNode | None) -> ListNode | None:
    if head.val >= 5:
      head = ListNode(0, head)

    curr = head

    while curr:
      curr.val *= 2
      curr.val %= 10
      if curr.next and curr.next.val >= 5:
        curr.val += 1
      curr = curr.next

    return head