链表实现读取两个超大数相加
时间: 2023-07-11 07:21:19 浏览: 52
首先,我们可以将两个超大数存储在链表中,每个节点存储一个数位。为了方便计算,我们可以将两个链表逆序,这样从头到尾遍历时,数位的高位就在前面,低位在后面。
接下来,我们可以用一个变量 `carry` 来记录进位,并且从头到尾遍历两个链表,将对应节点的数位相加,再加上上一次计算的进位。如果两个链表长度不一致,那么短的链表的节点数位默认为 0。
计算结果对 10 取模,得到当前位的数值,并且更新进位值。将计算结果存储在一个新的链表中,最后如果还有进位,需要将其添加到链表末尾。
下面是具体实现的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
l1 = reverseList(l1)
l2 = reverseList(l2)
dummy = ListNode(0)
cur = dummy
carry = 0
while l1 or l2:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
s = val1 + val2 + carry
cur.next = ListNode(s % 10)
carry = s // 10
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if carry:
cur.next = ListNode(carry)
return reverseList(dummy.next)
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
```
这个实现可以处理链表中任意长度的数,并且可以处理进位的情况。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)