难度:中等
题目内容:
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
示例:
输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 8 -> 0 -> 7
题解:
emmm
首先最简单的情况就是有数为0 ,直接返回另一个就好了
其他的情况可以先把列表翻转过来,然后相加的出一个新列表,把新列表再翻转一下就得到结果了。
不过题目要求不能进行翻转
emmm那也好说,我们加一个位数计数就好了
不过要注意的是(反正我出错了)相加是可能进多位的(199+1这样)
我下面这个就算初步修改了一下,但是只能解决进两位。。。所以打算换种方法,先算出来,然后把中间变成两位的数拆开就好了嘛,比如10拆成1 0
# 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:
###如果有0的话
if l1.val == 0:
return l2
elif l2.val == 0:
return l1
l1len = 0
l1c = l1
while l1c:
l1c = l1c.next
l1len += 1
l2len = 0
l2c = l2
while l2c :
l2c = l2c.next
l2len += 1
if l2len >= l1len:
return self.sum(l2,l2len,l1,l1len)
elif l2len < l1len:
return self.sum(l1,l1len,l2,l2len)
def sum(self,lbig,lbiglen,lsmall,lsmalllen):
# if lbiglen == lsmalllen and (lbig.val +lsmall.val) >= 10:
# r = ListNode(1)
r0 = ListNode(0)
r = r0
while lbig:
if lbiglen == lsmalllen:
if (lbig.val +lsmall.val) >= 10:
r.val += 1
r.next = ListNode(mod( (lbig.val +lsmall.val) ,10))
if r.next.val == 9:#预警一下会不会连进两位
temp = r
r = r.next
lbig = lbig.next
lbiglen -= 1
lsmall = lsmall.next
lsmalllen -= 1
else:
r.next = ListNode(lbig.val)
if r.next.val == 9:#预警一下会不会连进两位
temp = r
r = r.next
lbig = lbig.next
lbiglen -= 1
if r0.val == 0 and r0.next:
r0 = r0.next
return r0
稍加改动,就可以通过啦!
# 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:
###如果有0的话
if l1.val == 0:
return l2
elif l2.val == 0:
return l1
l1len = 0
l1c = l1
while l1c:
l1c = l1c.next
l1len += 1
l2len = 0
l2c = l2
while l2c :
l2c = l2c.next
l2len += 1
if l2len >= l1len:
return self.sum(l2,l2len,l1,l1len)
elif l2len < l1len:
return self.sum(l1,l1len,l2,l2len)
def sum(self,lbig,lbiglen,lsmall,lsmalllen):
# if lbiglen == lsmalllen and (lbig.val +lsmall.val) >= 10:
# r = ListNode(1)
r0 = ListNode(0)
r = r0
while lbig:
if lbiglen == lsmalllen:
if (lbig.val +lsmall.val) >= 10:
r.val += 1
r.next = ListNode(mod( (lbig.val +lsmall.val) ,10))
r = r.next
lbig = lbig.next
lbiglen -= 1
lsmall = lsmall.next
lsmalllen -= 1
else:
r.next = ListNode(lbig.val)
r = r.next
lbig = lbig.next
lbiglen -= 1
if r0.val == 0 and r0.next:
r0 = r0.next
# 拆数
l = lbiglen
r = r0
carry = True
while carry:
carry = False
r = r0
while r.next:
if r.next.val >= 10:
r.val += 1
r.next.val -= 10
carry = True
r = r.next
# 第一位大于等于10要变成两个数
if r0.val >= 10:
newNode = ListNode(mod(r0.val,10))
newNode.next = r0.next
r0.val = r0.val // 10
r0.next = newNode
l += 1
return r0
网友评论