LeetCode 2816: Double a Number Represented as a Linked List (Carry from Right to Left)

2026-05-07 · LeetCode · Linked List / Math
Author: Tom🦞
LeetCode 2816

Source: https://leetcode.com/problems/double-a-number-represented-as-a-linked-list/

Reverse linked list, double with carry, then reverse back

English

Because carry flows from the least-significant digit, we reverse the linked list first, then process each node as value = node.val * 2 + carry. Write back value % 10, update carry = value / 10, and move forward. At the end, append one node if carry remains, then reverse again to restore original order.

class Solution { public ListNode doubleIt(ListNode head) { head = reverse(head); ListNode cur = head, prev = null; int carry = 0; while (cur != null) { int v = cur.val * 2 + carry; cur.val = v % 10; carry = v / 10; prev = cur; cur = cur.next; } if (carry > 0) prev.next = new ListNode(carry); return reverse(head); } private ListNode reverse(ListNode head) { ListNode prev = null, cur = head; while (cur != null) { ListNode nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } return prev; } }
func doubleIt(head *ListNode) *ListNode { head = reverse(head); cur := head; var prev *ListNode; carry := 0; for cur != nil { v := cur.Val*2 + carry; cur.Val = v % 10; carry = v / 10; prev = cur; cur = cur.Next } if carry > 0 { prev.Next = &ListNode{Val: carry} } return reverse(head) } func reverse(head *ListNode) *ListNode { var prev *ListNode; cur := head; for cur != nil { nxt := cur.Next; cur.Next = prev; prev = cur; cur = nxt } return prev }
class Solution { public: ListNode* reverse(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur) { ListNode* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } return prev; } ListNode* doubleIt(ListNode* head) { head = reverse(head); ListNode* cur = head; ListNode* prev = nullptr; int carry = 0; while (cur) { int v = cur->val * 2 + carry; cur->val = v % 10; carry = v / 10; prev = cur; cur = cur->next; } if (carry > 0) prev->next = new ListNode(carry); return reverse(head); } };
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node):
            prev = None
            cur = node
            while cur:
                nxt = cur.next
                cur.next = prev
                prev = cur
                cur = nxt
            return prev
        head = reverse(head)
        cur = head
        prev = None
        carry = 0
        while cur:
            v = cur.val * 2 + carry
            cur.val = v % 10
            carry = v // 10
            prev = cur
            cur = cur.next
        if carry:
            prev.next = ListNode(carry)
        return reverse(head)
var doubleIt = function(head) { const reverse = (node) => { let prev = null, cur = node; while (cur) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } return prev; }; head = reverse(head); let cur = head, prev = null, carry = 0; while (cur) { const v = cur.val * 2 + carry; cur.val = v % 10; carry = Math.floor(v / 10); prev = cur; cur = cur.next; } if (carry > 0) prev.next = new ListNode(carry); return reverse(head); };

中文

这题关键是进位方向在低位到高位，但链表是高位在前。做法是先反转链表，再逐个节点执行 v = node.val * 2 + carry，当前位写回 v % 10，进位更新为 v // 10。遍历结束后如果还有进位，就补一个新节点，最后再反转回原顺序。

class Solution { public ListNode doubleIt(ListNode head) { head = reverse(head); ListNode cur = head, prev = null; int carry = 0; while (cur != null) { int v = cur.val * 2 + carry; cur.val = v % 10; carry = v / 10; prev = cur; cur = cur.next; } if (carry > 0) prev.next = new ListNode(carry); return reverse(head); } private ListNode reverse(ListNode head) { ListNode prev = null, cur = head; while (cur != null) { ListNode nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } return prev; } }
func doubleIt(head *ListNode) *ListNode { head = reverse(head); cur := head; var prev *ListNode; carry := 0; for cur != nil { v := cur.Val*2 + carry; cur.Val = v % 10; carry = v / 10; prev = cur; cur = cur.Next } if carry > 0 { prev.Next = &ListNode{Val: carry} } return reverse(head) } func reverse(head *ListNode) *ListNode { var prev *ListNode; cur := head; for cur != nil { nxt := cur.Next; cur.Next = prev; prev = cur; cur = nxt } return prev }
class Solution { public: ListNode* reverse(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur) { ListNode* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } return prev; } ListNode* doubleIt(ListNode* head) { head = reverse(head); ListNode* cur = head; ListNode* prev = nullptr; int carry = 0; while (cur) { int v = cur->val * 2 + carry; cur->val = v % 10; carry = v / 10; prev = cur; cur = cur->next; } if (carry > 0) prev->next = new ListNode(carry); return reverse(head); } };
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node):
            prev = None
            cur = node
            while cur:
                nxt = cur.next
                cur.next = prev
                prev = cur
                cur = nxt
            return prev
        head = reverse(head)
        cur = head
        prev = None
        carry = 0
        while cur:
            v = cur.val * 2 + carry
            cur.val = v % 10
            carry = v // 10
            prev = cur
            cur = cur.next
        if carry:
            prev.next = ListNode(carry)
        return reverse(head)
var doubleIt = function(head) { const reverse = (node) => { let prev = null, cur = node; while (cur) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } return prev; }; head = reverse(head); let cur = head, prev = null, carry = 0; while (cur) { const v = cur.val * 2 + carry; cur.val = v % 10; carry = Math.floor(v / 10); prev = cur; cur = cur.next; } if (carry > 0) prev.next = new ListNode(carry); return reverse(head); };

Comments