难度: Medium
Submission
运行时间: 24 ms
内存: 0.0 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def plusOne(self, head: ListNode) -> ListNode:
if head.val == 0: return ListNode(1)
def dfs(head):
if not head: return 1
remainder = dfs(head.next)
summation = head.val + remainder
head.val = summation % 10
return summation // 10
remainder = dfs(head)
if remainder > 0:
newHead = ListNode(remainder)
newHead.next = head
return newHead
return head
Explain
这个题解使用了递归的方法。首先检查头节点的值是否为0，如果是则直接返回一个值为1的新节点。否则进入递归函数dfs，从链表的尾部开始，将每个节点的值加上一个进位值（初始为1），计算结果对10取模作为新的节点值，并将进位值传递给下一层递归。递归结束后，如果最后的进位值大于0，则在链表头部新增一个节点来容纳这个进位。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def plusOne(self, head: ListNode) -> ListNode:
# 如果头节点的值为0，直接返回一个值为1的新节点
if head.val == 0: return ListNode(1)
def dfs(head):
# 递归的基础情况：如果当前节点为空，返回初始进位值1
if not head: return 1
# 递归处理下一个节点，并获取返回的进位值
remainder = dfs(head.next)
# 将当前节点的值与进位相加
summation = head.val + remainder
# 对相加的结果取模，作为当前节点的新值
head.val = summation % 10
# 返回新的进位值
return summation // 10
# 从头节点开始递归处理链表
remainder = dfs(head)
# 如果最后还有进位，则在链表头部新增一个节点
if remainder > 0:
newHead = ListNode(remainder)
newHead.next = head
return newHead
# 否则直接返回原链表头节点
return head
Explore
在头节点值为0的情况下，通常表示整个链表只有一个节点，且该节点的值为0。这是链表表示数字'0'的一种特殊情况。对于'加一'的操作，结果应该是'1'。继续递归处理整个链表在这种情况下是不必要的，因为我们已经知道结果只能是'1'。直接返回一个值为1的新节点是一种更简洁有效的处理方式。
在递归函数中当当前节点为空时返回进位值1，是因为我们已经到达了链表的末尾，而整个操作是为了在链表末尾加一。在递归的最底层（即链表的最后一个节点之后），返回进位值1正是为了将这个'加一'操作传递回链表的最后一个节点。如果返回0，则表示没有进位，这与操作'加一'的目的不符。
递归处理确保链表顺序不发生逆转的关键在于它处理节点的方式。递归函数是首先递归调用自身处理下一个节点，直到链表末尾，然后在递归返回阶段，从链表的末尾开始向前逐个处理节点的值和进位。这种自底向上的处理方式确保了虽然处理是从链表尾部开始，但链表的物理结构并没有改变，保持了单链表的顺序。
如果最后的进位值大于0，通常发生在链表表示的数字每一位都是9的情况下。例如链表1 -> 9 -> 9，加一操作将其变为2 -> 0 -> 0，并产生一个新的进位1，这时需要在链表头部新增一个节点来容纳这个进位。这种情况是因为链表中的每一位加一后变成了10，需要向前进位。