python实现计算两个单链表所代表的数之和
程序员文章站
2022-03-03 21:13:43
python实现计算两个单链表所代表的数之和华为笔试题目描述:给定两个单链表,链表的每个结点代表一位数,计算两个数的和。例如 :输入链表 (3一>1一>5)和链表(5一>9一>2),输出 : 8->0->8, 即 513+295=808, 注意个位数在链表头。链表相加法主要思路 : 对链表中的结点直接进行相加操作,把相加的和存储到新的链表中对应 的结 点中,同时还要记录结点相加后的进位。 如下图所示 :使用这种方法需要注意如下几个问题: Cl)每组结点进行...
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
上一篇: Python最新版本安装
下一篇: Pytorch的Tensor操作(1)