leetcode 链表求和两种方法迭代和递归 LeetCode

面试题 02.05. 链表求和 https://leetcode-cn.com/problems/sum-lists-lcci/
给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912

# Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def addTwoNumbers(self, l1, l2):head = ListNode(0) curr = head temp = 0while l1 and l2: # l1 and l2 are not None numsum = l1.val + l2.val + temp temp = numsum // 10 curr.next = ListNode(numsum % 10) curr = curr.next l1, l2 = l1.next, l2.next# l1 or l2 is None rest = l1 if l1 else l2while rest and temp: numsum = temp + rest.val temp = numsum // 10 curr.next = ListNode(numsum % 10) curr = curr.next rest = rest.nextif not temp and not rest: # temp and rest are both None pass elif not temp: # rest still exist curr.next = rest elif not rest: # temp is not 0 curr.next = ListNode(temp) return head.next

结果还凑活吧

文章图片

【leetcode 链表求和两种方法迭代和递归】这道题主要是分三步:
第一步:两个链表都不为空的时候, 那就是三者直接相加, 之和不会超过19, 所以取余%10 为当前位的数值, 整除10 为进位
第二步:当两个链表至少有一个为空时, 先假设有一个链表存在, 将其与进位进行继续之前的操作, 只是现在是两个相加
第三步:判断第二步终止的情况, 处理结尾
直接返回链表的头即可

第二种方法递归

class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: return self.addTwoNumbers2(l1, l2, 0)def addTwoNumbers2(self, l1, l2, z): if l1 is None and l2 is None and z == 0: return Noneif l1 is None: l1 = ListNode(0)if l2 is None: l2 = ListNode(0)value = https://www.it610.com/article/l1.val + l2.val + z result = ListNode(value % 10) result.next = self.addTwoNumbers2(l1.next, l2.next, value//10) return result

效率也还可以: