leetcode_445. 两数相加 II
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
...
目录
一、题目内容
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
示例:
输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 8 -> 0 -> 7
二、解题思路
哎,太难了,还是两个函数来回套吧:
1.两数相加:leetcode_2. 两数相加
2.反转链表:leetcode_206. 反转链表
三、代码
-
# Definition for singly-linked list.
-
class ListNode:
-
def __init__(self, x):
-
self.val = x
-
self.next = None
-
-
class Solution:
-
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
-
head = self._addTwoNumbers(self.reverseList(l1), self.reverseList(l2))
-
return self.reverseList(head)
-
-
def _addTwoNumbers(self, l1, l2):
-
"""
-
:type l1: ListNode
-
:type l2: ListNode
-
:rtype: ListNode
-
"""
-
head = ListNode(0)
-
# print(head.val, head.next)
-
p = head
-
q = p
-
carry = 0
-
while l1 or l2:
-
-
if l1 is not None:
-
l1_val = l1.val
-
# print("l1:", l1_val)
-
else:
-
l1_val = 0
-
if l2 is not None:
-
l2_val = l2.val
-
# print("l2:", l2_val)
-
else:
-
l2_val = 0
-
temp = l1_val + l2_val + carry
-
if temp >= 10:
-
carry = 1
-
p.val = temp - 10
-
p.next = ListNode(1)
-
else:
-
carry = 0
-
p.val = temp
-
p.next = ListNode(0)
-
q = p
-
p = p.next
-
if l1 is not None:
-
l1 = l1.next
-
if l2 is not None:
-
l2 = l2.next
-
if q.next.val == 0:
-
q.next = None
-
del p
-
return head
-
-
def reverseList(self, head: ListNode):
-
# null 1 --> 2 --> 3 --> 4 --> null
-
# null <-- 1 <-- 2 <-- 3 <-- 4 null
-
if not head:
-
return None
-
cur, cur_new_next = head, None
-
while cur:
-
# save original next node
-
origin_next = cur.next
-
# link new next node
-
cur.next = cur_new_next
-
# current node turns to new next node
-
cur_new_next = cur
-
# original next node turns to current node
-
cur = origin_next
-
return cur_new_next
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/110231369
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)