我要评论python实现计算两个单链表所代表的数之和
华为笔试
题目描述:
给定两个单链表，链表的每个结点代表一位数，计算两个数的和。例如 :输入链表 (3一>
1一>5)和链表(5一>9一>2)，输出 : 8->0->8， 即 513+295=808， 注意个位数在链表头。
链表相加法
主要思路 : 对链表中的结点直接进行相加操作，把相加的和存储到新的链表中对应 的结 点中，同时还要记录结点相加后的进位。 如下图所示 :
使用这种方法需要注意如下几个问题: Cl)每组结点进行相加后需要记录其是否有进位 ; (2)如果两个链表 hl 与 h2 的长度不同(长度分别为 Ll 和 L2，且 Ll<L刀， 当对链表的第 Ll 位计算完成后，接下来只需要考虑链表 L2 剩余的结点的值(需要考虑进位); (3)对链表 所有结点都完成计算后，还需要考虑此时是否还有进位，如果有进位，则需要增加新的结点， 此结点的数据域为 l。实现代码如下:
首先实现链表的一些功能：
class SingleNode(object):
"""单链表的结点"""
def __init__(self,item):
# _item存放数据元素
self.item = item
# _next是下一个节点的标识
self.next = None
class LinkedList(object):
"""单链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head == None
def add(self, item):
"""尾部添加元素"""
node = SingleNode(item)
# 先判断链表是否为空，若是空链表，则将_head指向新节点
if self.is_empty():
self._head = node
# 若不为空，则找到尾部，将尾节点的next指向新节点
else:
cur = self._head
while cur.next != None:
cur = cur.next
cur.next = node
def print_link(self):
cur=self._head
if cur==None:
return None
while cur:
print(cur.item)
cur=cur.next
实现主要功能：
def doubleLinkAdd(head1, head2):
# 如果有一个链表为空，直接返回另外一个链表
if head1 is None:
return head2
if head2 is None:
return head1
# 引入变量及初始化，c表示进位，resultLink存储相加后的节点，cur1, cur2为操作的指针
c = 0
resultLink = LinkedList()
cur1 = head1
cur2 = head2
# 循环依次相加对应节点的值，结果添加到resultLink
while cur1 is not None and cur2 is not None:
sums = cur1.item + cur2.item + c
c = sums // 10 # 整除，例：27//10=2, 表示进位
tmp = sums % 10 # 取余，例：27%10=7，表示相加结果的个位数的值
resultLink.add(tmp)
cur1 = cur1.next
cur2 = cur2.next
# 如果链表1更长，将剩余节点加入到结果链表中
if cur1 is not None:
while cur1:
sums = cur1.item + c
c = sums // 10
tmp = sums % 10
resultLink.add(tmp)
cur1 = cur1.next
# 如果链表2更长，将剩余节点加入到结果链表中
if cur2 is not None:
while cur2:
sums = cur2.item + c
c = sums // 10
tmp = sums % 10
resultLink.add(tmp)
cur2 = cur2.next
# 判断是否还有进位，有进位则加入链表
if c > 0:
resultLink.add(c)
return resultLink
测试：
if __name__ == "__main__":
print("============link1===========")
link1 = LinkedList()
link1.add(3)
link1.add(4)
link1.add(5)
link1.add(6)
link1.add(7)
link1.add(8)
link1.print_link()
print("============link2===========")
link2 = LinkedList()
link2.add(9)
link2.add(8)
link2.add(7)
link2.add(6)
link2.add(5)
link2.print_link()
print("============resultLink===========")
doubleLinkAdd(link1._head, link2._head).print_link()
输出：
============link1===========
3
4
5
6
7
8
============link2===========
9
8
7
6
5
============resultLink===========
2
3
3
3
3
9
本文地址：https://blog.csdn.net/weixin_42813521/article/details/107648691
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论