给单链表加一

[编程题]给单链表加一

热度指数：2568 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个用单链表表示的整数，然后把这个整数加一。

数据范围：链表长度满足 $1 \le n \le 1000 \$ ，链表上每个节点的值满足 $0 \le val \le 9 \$ ，可以保证链表在非 0 的情况下没有前导零

例如输入{1,2,3}时，对应的输出为{1,2,4}，转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{1,2,4}

示例2

输入

{1,2,0}

输出

{1,2,1}

示例3

输入

{9}

输出

{1,0}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Python3

tangjunjun

class Solution:
    def plusOne(self , head: ListNode) -> ListNode:
        # write code here
        a=[]
        while head:
            a.append(head)
            head=head.next
        is_add=True
        for i in range(len(a)):
            if is_add:
                val_new = a[-i-1].val+1
                a[-i-1].val=val_new
            if val_new>=10:
                a[-i-1].val=val_new-10
            else:
                head_new=a[0]
                break
            if i==len(a)-1:
                head_new=ListNode(1)
                head_new.next=a[0]
        return head_new

发表于 2021-11-23 00:08:17 回复(0)

Python3

NightRunner

    def plusOne(self, head: ListNode) -> ListNode:
        # 找到不是9的最小位
        p, min_pos = head, None
        while p:
            if p.val != 9:
                min_pos = p
            p = p.next
        # 处理都是9的情况, 最高位前面创建一个节点0
        if not min_pos:
            min_pos = ListNode(0)
            min_pos.next = head
            head = min_pos
        min_pos.val += 1
        # 处理min_pos后面的值，都是9，要改成0
        p = min_pos.next
        while p:
            p.val = 0
            p = p.next
        return head

发表于 2021-11-12 17:13:15 回复(0)