Medium

题目描述

给你一个非空链表的头节点 head，表示一个不含前导零的非负整数。

返回将其表示的数字翻倍后的链表头节点。

示例 1：

输入：head = [1,8,9]
输出：[3,7,8]
解释：上图对应于给定的链表，表示数字 189。因此，返回的链表表示数字 189 * 2 = 378。

示例 2：

输入：head = [9,9,9]
输出：[1,9,9,8]
解释：上图对应于给定的链表，表示数字 999。因此，返回的链表表示数字 999 * 2 = 1998。

约束条件：

  • 链表中节点的数量在范围 [1, 10^4] 内
  • 0 <= Node.val <= 9
  • 输入保证链表表示的数字不含前导零，除了数字 0 本身

提示：

  • 从最低有效位到最高有效位遍历链表，将每个节点的值乘以 2
  • 处理翻倍过程中可能产生的进位
  • 如果最高位有进位，创建一个新节点并将其指向给定链表的开头

解题思路

这道题要求我们将链表表示的数字翻倍。有几种解法思路：

方法1：栈 + 进位处理 由于链表是从高位到低位存储，而加法需要从低位开始计算，我们可以使用栈来逆序处理。先将所有节点压栈，然后从栈顶开始弹出（相当于从个位开始），对每位乘以2并处理进位。

方法2：递归 使用递归可以天然地实现从低位到高位的处理。递归到链表末尾，然后在回溯过程中处理每一位的翻倍和进位。

方法3：反转链表 先反转链表，然后从头开始处理翻倍和进位，最后再反转回来。

推荐使用递归方法，代码简洁且易理解。递归函数返回进位值，在处理当前节点时将当前值乘以2加上来自低位的进位，然后更新当前节点值并返回新的进位。如果最终还有进位，就在链表头部添加新节点。

代码实现

class Solution {
public:
    ListNode* doubleIt(ListNode* head) {
        int carry = helper(head);
        if (carry) {
            return new ListNode(carry, head);
        }
        return head;
    }
    
private:
    int helper(ListNode* node) {
        if (!node) return 0;
        
        int carry = helper(node->next);
        int sum = node->val * 2 + carry;
        node->val = sum % 10;
        return sum / 10;
    }
};

class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def helper(node):
            if not node:
                return 0
            
            carry = helper(node.next)
            total = node.val * 2 + carry
            node.val = total % 10
            return total // 10
        
        carry = helper(head)
        if carry:
            return ListNode(carry, head)
        return head

public class Solution {
    public ListNode DoubleIt(ListNode head) {
        int carry = Helper(head);
        if (carry > 0) {
            return new ListNode(carry, head);
        }
        return head;
    }
    
    private int Helper(ListNode node) {
        if (node == null) return 0;
        
        int carry = Helper(node.next);
        int sum = node.val * 2 + carry;
        node.val = sum % 10;
        return sum / 10;
    }
}

var doubleIt = function(head) {
    function helper(node) {
        if (!node) return 0;
        
        const carry = helper(node.next);
        const sum = node.val * 2 + carry;
        node.val = sum % 10;
        return Math.floor(sum / 10);
    }
    
    const carry = helper(head);
    if (carry) {
        return new ListNode(carry, head);
    }
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度递归方法
时间复杂度O(n)
空间复杂度O(n)

其中 n 是链表的长度。时间复杂度为 O(n) 是因为需要遍历每个节点一次。空间复杂度为 O(n) 是由于递归调用栈的深度与链表长度成正比。

相关题目