Python两数相加实现

  • 题目要求：

  • 思路：

    • 遍历第一个与第二个链表，把相同位置的相加

    • 设置一个flag，用来标记相加后大于10的部分，下一位再相加时，就要加上flag的值

    • 遍历至一个链表结束

    • 如果此时flag不为0，把未结束的链表当前的第一位加上flag

    • falg记录相加大于10的部分

    • 直至当前列表也遍历完

    • 如果遍历完，flag仍然不为0，再补一位1

  • 核心代码：

    • 遍历两个链表：

# 把链表1 2 的头赋给h1，h2

h1 = l1

h2 = l2

# 创建新链表，用来保存计算完的数

l3 = ListNode()

h3 = l3

# flag标志两数加完大于9的部分

flag = 0

# 遍历两个链表，h3当前的值为h1+h2去掉十位的部分，flag保存进位，运算完h1，h2，h3移向下一位

while h1 and h2 :

h3.next = ListNode((h1.val + h2.val + flag) % 10)

flag = (h1.val + h2.val + flag) // 10

h1 = h1.next

h2 = h2.next

h3 = h3.next

- 如果链表1或2未遍历完:

#原理如上
if h1 :
    while h1 :
        h3.next = ListNode((h1.val + flag) % 10)
        flag = (h1.val + flag) // 10
        h1 = h1.next
        h3 = h3.next
# 用elif，如果是h1有未遍历的，遍历结束后就不遍历h2了
elif h2 :
    while h2 :
        h3.next = ListNode((h2.val + flag) % 10)
        flag = (h2.val + flag) // 10
        h2 = h2.next
        h3 = h3.next

- 如果最后一位相加后，仍需进位：

        if flag == 1:
            h3.next = ListNode(1)

  • 完整代码：加上判断l1和l2一开始是否为空，如果l1为空，返回l2，如果l2为空，返回l1

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        h1 = l1
        h2 = l2 
        l3 = ListNode()
        h3 = l3
        flag = 0
        while h1 and h2 :
            h3.next = ListNode((h1.val + h2.val + flag) % 10)
            flag = (h1.val + h2.val + flag) // 10
            h1 = h1.next
            h2 = h2.next   
            h3 = h3.next
        if h1 :
            while h1 :
                h3.next = ListNode((h1.val + flag) % 10)
                flag = (h1.val + flag) // 10
                h1 = h1.next
                h3 = h3.next
        elif h2 :
            while h2 :
                h3.next = ListNode((h2.val + flag) % 10)
                flag = (h2.val + flag) // 10
                h2 = h2.next
                h3 = h3.next
        if flag == 1:
            h3.next = ListNode(1)
        return l3.next

以上是 Python两数相加实现 的全部内容， 来源链接： utcz.com/a/13681.html

回到顶部