链表相加(二)
问题简述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。思路1：转成数值计算（超时）
Python
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head1 ListNode类
# @param head2 ListNode类
# @return ListNode类
#
class Solution:
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
# write code here
def get_v(cur):
ret = 0
while cur:
ret = ret * 10 + cur.val
cur = cur.next
return ret
s = get_v(head1) + get_v(head2)
s = str(s)
dummy = cur = ListNode(0)
for c in s:
cur.next = ListNode(int(c))
cur = cur.next
return dummy.next思路2：利用栈
Python
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head1 ListNode类
# @param head2 ListNode类
# @return ListNode类
#
class Solution:
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
# write code here
def get_v(x):
ret = []
while x:
ret.append(x.val)
x = x.next
return ret
h1 = get_v(head1)
h2 = get_v(head2)
ret = []
ex = 0
while h1 or h2:
h1v = h1.pop() if h1 else 0
h2v = h2.pop() if h2 else 0
v = h1v + h2v + ex
ret.append(v % 10)
ex = v // 10
if ex:
ret.append(1)
dummy = cur = ListNode(0)
while ret:
cur.next = ListNode(ret.pop())
cur = cur.next
return dummy.next思路3：反转链表后逐位相加（推荐）
Python
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head1 ListNode类
# @param head2 ListNode类
# @return ListNode类
#
class Solution:
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
# def pp(x):
# """打印链表（调试用）"""
# tmp = []
# while x:
# tmp.append(x.val)
# x = x.next
# print(tmp)
def reverse(x):
"""反转链表"""
pre, cur = None, x
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
h1 = reverse(head1)
h2 = reverse(head2)
cur = dummy = ListNode(0)
ex = 0 # 进位
# 合并 h1 和 h2 的判断
while h1 or h2:
h1v = h1.val if h1 else 0
h2v = h2.val if h2 else 0
v = h1v + h2v + ex
node = ListNode(v % 10)
ex = v // 10
cur.next = node
cur = cur.next
h1 = h1.next if h1 else None
h2 = h2.next if h2 else None
# 将下面两段合并到一起
# ex = 0
# while h1 and h2:
# v = h1.val + h2.val + ex
# node = ListNode(v % 10)
# ex = v // 10
# cur.next = node
# cur = cur.next
# h1 = h1.next
# h2 = h2.next
# h = h1 if h1 else h2
# while h:
# v = h.val + ex
# node = ListNode(v % 10)
# ex = v // 10
# cur.next = node
# cur = cur.next
# h = h.next
# 如果还存在进位
if ex:
cur.next = ListNode(1)
ret = dummy.next
return reverse(ret) # 注意最后再反转一次Last updated