链表使用的专题
2.两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
思路:
(思路可能描述的不是很好,不想看可以直接看代码)
0.初始定义两个双指针l1,l2,分别指向两个链表的头结点。
定义一个哑结点,定义一个node指针指向哑结点。
1.对两个指针指向的结点的值(若非空则为当前值,否则为0)相加。当前位的值为相加之后对10取余,进的数为对10整除。
1.1.若相加之后大于9,需要向下一位进1。而下一位的值相加的时候还要考虑是否有前一位的进1。因此,我们还要初始化一个count = 0,表示需要向下一位进的数。
1.2.若相加之后小于等于9,无需进1.
2.node.next 为以1.中求得的值构造的结点,更新node = node.next
更新l1 = l1.next if l1 else None,l2 = l2.next if l2 else None
3.重复步骤1,2,直到l1,l2都为空,且count为0.
代码如下:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
count = 0 # 要进位的值
head = ListNode(None) # 哑结点
node = head # 指向哑结点的指针
while l1 or l2 or count:
a1 = l1.val if l1 else 0 # l1指向的结点的值
a2 = l2.val if l2 else 0 # l2指向的结点的值
sum = a1 + a2 + count # 还有加上进位的值
node.next = ListNode(sum%10) # 构造当前结点
count = sum//10 # 更新进位的值
node = node.next # 更新要返回的链表的指针
l1 = l1.next if l1 else None # 更新l1指针
l2 = l2.next if l2 else None # 更新l2指针
return head.next # 返回哑结点的下一位结点
本文地址:https://blog.csdn.net/weixin_45276525/article/details/109648276
上一篇: 2020-11-03
下一篇: 学习深度学习课程前景怎么样?