0369：给单链表加一（★）

2016-01-04 约 229 字预计阅读 1 分钟次阅读

力扣第 369 题

题目

给定一个用链表表示的非负整数，然后将这个整数 再加上 1 。

这些数字的存储是这样的：最高位有效的数字位于链表的首位 head 。

示例 1:

输入: head = [1,2,3]
输出: [1,2,4]

示例 2:

输入: head = [0]
输出: [1]

提示：

链表中的节点数在 [1, 100] 的范围内。
0 <= Node.val <= 9
由链表表示的数字不包含前导零，除了零本身。

分析

可以类似 0066，先转为数组，模拟进位加分后再转为链表。也可以用递归，直接修改节点值。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def plusOne(self, head: ListNode) -> ListNode:
	def dfs(node):
		if not node:
			return 1
		s = node.val + dfs(node.next)
		node.val = s % 10
		return s // 10
	
	carry = dfs(head)
	return ListNode(1, next=head) if carry else head

28 ms

目录

0369：给单链表加一（★）

题目

分析

解答