翻倍以链表形式表示的数字

6914. 翻倍以链表形式表示的数字

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

将链表翻倍后，返回头节点 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⁴] 内
0 <= Node.val <= 9
生成的输入满足：链表表示一个不含前导零的数字，除了数字 0 本身。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* doubleIt(ListNode* head) { } };

javascript 解法, 执行用时: 168 ms, 内存消耗: 50.9 MB, 提交时间: 2023-08-14 09:38:54

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var doubleIt = function(head) {
    if (head.val > 4)
        head = new ListNode(0, head);
    for (var cur = head; cur != null; cur = cur.next) {
            cur.val = cur.val * 2 % 10;
            if (cur.next != null && cur.next.val > 4)
                cur.val++;
    }
    return head;
};

java 解法, 执行用时: 2 ms, 内存消耗: 43.8 MB, 提交时间: 2023-08-14 09:37:47

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head.val > 4)
            head = new ListNode(0, head);
        for (var cur = head; cur != null; cur = cur.next) {
            cur.val = cur.val * 2 % 10;
            if (cur.next != null && cur.next.val > 4)
                cur.val++;
        }
        return head;
    }
}

cpp 解法, 执行用时: 300 ms, 内存消耗: 113.3 MB, 提交时间: 2023-08-14 09:37:24

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *doubleIt(ListNode *head) {
        if (head->val > 4)
            head = new ListNode(0, head);
        for (auto cur = head; cur; cur = cur->next) {
            cur->val = cur->val * 2 % 10;
            if (cur->next && cur->next->val > 4)
                cur->val++;
        }
        return head;
    }
};

golang 解法, 执行用时: 88 ms, 内存消耗: 7 MB, 提交时间: 2023-08-14 09:36:43

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func doubleIt(head *ListNode) *ListNode {
	if head.Val > 4 {
		head = &ListNode{0, head}
	}
	for cur := head; cur != nil; cur = cur.Next {
		cur.Val = cur.Val * 2 % 10
		if cur.Next != nil && cur.Next.Val > 4 {
			cur.Val++
		}
	}
	return head
}

python3 解法, 执行用时: 312 ms, 内存消耗: 19.6 MB, 提交时间: 2023-08-14 09:35:55

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
'''
不考虑进位，则每个节点*2；考虑进位，只有当节点值大于4会进位，进位则加一个节点。
'''
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.val > 4:
            head = ListNode(0, head)
        cur = head
        while cur:
            cur.val = cur.val * 2 % 10
            if cur.next and cur.next.val > 4:
                cur.val += 1
            cur = cur.next
        return head

golang 解法, 执行用时: 72 ms, 内存消耗: 7.2 MB, 提交时间: 2023-08-14 09:34:36

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 206. 反转链表
// 视频讲解 https://www.bilibili.com/video/BV1sd4y1x7KN/
func reverseList(head *ListNode) *ListNode {
	var pre, cur *ListNode = nil, head
	for cur != nil {
		nxt := cur.Next
		cur.Next = pre
		pre = cur
		cur = nxt
	}
	return pre
}

// 2. 两数相加：自己和自己相加
// 题解 https://leetcode.cn/problems/add-two-numbers/solution/dong-hua-jian-ji-xie-fa-cong-di-gui-dao-oe0di/
func double(l1 *ListNode) *ListNode {
	dummy := &ListNode{} // 哨兵节点，作为新链表的头节点的前一个节点
	cur := dummy
	carry := 0 // 进位
	for l1 != nil {
		carry += l1.Val * 2                   // 节点值和进位加在一起
		cur.Next = &ListNode{Val: carry % 10} // 每个节点保存一个数位
		carry /= 10                           // 新的进位
		cur = cur.Next                        // 下一个节点
		l1 = l1.Next                          // 下一个节点
	}
	if carry != 0 {
		cur.Next = &ListNode{Val: carry}
	}
	return dummy.Next
}

func doubleIt(head *ListNode) *ListNode {
	head = reverseList(head)
	res := double(head) // 反转后，就变成【2. 两数相加】了
	return reverseList(res)
}

python3 解法, 执行用时: 516 ms, 内存消耗: 21.6 MB, 提交时间: 2023-08-14 09:33:51

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 看做是两个head相加
# https://space.bilibili.com/206214
class Solution:
    # 206. 反转链表
    # 视频讲解 https://www.bilibili.com/video/BV1sd4y1x7KN/
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    # 2. 两数相加：自己和自己相加
    # 题解 https://leetcode.cn/problems/add-two-numbers/solution/dong-hua-jian-ji-xie-fa-cong-di-gui-dao-oe0di/
    def double(self, l1: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 哨兵节点
        carry = 0  # 进位
        while l1:  # 有一个不是空节点，或者还有进位，就继续迭代
            carry += l1.val * 2  # 节点值和进位加在一起
            cur.next = ListNode(carry % 10)  # 每个节点保存一个数位
            carry //= 10  # 新的进位
            cur = cur.next  # 下一个节点
            l1 = l1.next  # 下一个节点
        if carry:
            cur.next = ListNode(carry)
        return dummy.next  # 哨兵节点的下一个节点就是头节点

    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        head = self.reverseList(head)
        res = self.double(head)  # 反转后，就变成【2. 两数相加】了
        return self.reverseList(res)

上一题

下一题

详情