首页 > 其他分享 >力扣题解2-两数相加

力扣题解2-两数相加

时间：2024-07-29 17:40:12浏览次数：13  
标签：current head val 题解 self 链表 next 力扣 两数

问题的描述如下：

分析过程：

为了解决这个问题，我们需要逐位相加两个链表对应位置的值，并处理进位问题。具体步骤如下：

  1. 初始化一个新的链表，用于存储结果。
  2. 使用两个指针遍历两个输入链表，逐位相加，同时考虑进位。
  3. 如果一个链表比另一个短，则将其视为 0 进行计算。
  4. 处理最后可能存在的进位。

Python 实现：

首先，我们需要定义链表节点的类 ListNode，然后编写求和的函数 addTwoNumbers。

定义链表节点类：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

实现求和函数：

def addTwoNumbers(l1, l2):
    dummy_head = ListNode(0)  # 哨兵节点，便于返回结果链表
    current = dummy_head
    carry = 0  # 初始化进位为0

    while l1 is not None or l2 is not None:
        x = l1.val if l1 is not None else 0  # 获取l1的当前值，如果l1已经遍历完则取0
        y = l2.val if l2 is not None else 0  # 获取l2的当前值，如果l2已经遍历完则取0
        sum = carry + x + y  # 计算当前位的和，包括进位
        carry = sum // 10  # 更新进位
        current.next = ListNode(sum % 10)  # 创建新节点存储当前位的值
        current = current.next  # 移动到下一个节点

        if l1 is not None: l1 = l1.next  # 移动l1到下一个节点
        if l2 is not None: l2 = l2.next  # 移动l2到下一个节点

    if carry > 0:
        current.next = ListNode(carry)  # 如果最后有进位，创建新节点存储进位值

    return dummy_head.next  # 返回结果链表，跳过哨兵节点

# 示例
def create_linked_list(numbers):
    dummy_head = ListNode(0)
    current = dummy_head
    for number in numbers:
        current.next = ListNode(number)
        current = current.next
    return dummy_head.next

def print_linked_list(node):
    while node:
        print(node.val, end=' -> ' if node.next else '\n')
        node = node.next

l1 = create_linked_list([2, 4, 3])
l2 = create_linked_list([5, 6, 4])
result = addTwoNumbers(l1, l2)
print_linked_list(result)  # 输出：7 -> 0 -> 8

详细步骤：

  1. 初始化：

    • 创建一个哨兵节点 dummy_head，用于方便返回结果链表。
    • 设置一个指针 current 指向哨兵节点。
    • 初始化进位 carry 为 0。

  2. 遍历两个链表：

    • 在 l1 或 l2 未遍历完时，进行循环。
    • 获取当前节点的值 x 和 y，如果链表已经遍历完则取 0。
    • 计算当前位的和 sum = carry + x + y。
    • 更新进位 carry = sum // 10。
    • 创建新节点存储当前位的值 sum % 10，并将其链接到结果链表中。
    • 移动 current 指针到新创建的节点。
    • 如果 l1 未遍历完，则移动到下一个节点，同样处理 l2。

  3. 处理最后的进位：

    • 如果最后计算完还有进位，则创建一个新节点存储进位值。

  4. 返回结果链表：

    • 返回哨兵节点 dummy_head 的下一个节点，即结果链表的头节点。

这样，我们就可以通过这个函数将两个链表表示的数字相加，并以链表形式返回结果。

链表（Linked List）

链表是一种线性数据结构，其中的元素是节点（Node），每个节点包含数据和指向下一个节点的引用（或指针）。链表的长度可以动态变化，因此在需要频繁插入和删除操作的场景中非常有用。链表主要分为以下几种类型：

  1. 单向链表（Singly Linked List）
  2. 双向链表（Doubly Linked List）
  3. 循环链表（Circular Linked List）

单向链表

在单向链表中，每个节点只包含一个指向下一个节点的引用。链表的第一个节点称为头节点（Head），最后一个节点的 next 引用指向 None，表示链表的结束。

定义单向链表节点类

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点存储的数据
        self.next = next  # 指向下一个节点的引用

基本操作

  1. 初始化链表
  2. 插入节点
  3. 删除节点
  4. 遍历链表
class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 初始化链表，头节点为空

    def append(self, val):
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def delete(self, val):
        current = self.head
        if current and current.val == val:
            self.head = current.next
            current = None
            return
        prev = None
        while current and current.val != val:
            prev = current
            current = current.next
        if current is None:
            return
        prev.next = current.next
        current = None

    def traverse(self):
        current = self.head
        while current:
            print(current.val, end=" -> " if current.next else "\n")
            current = current.next

# 示例
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.traverse()  # 输出：1 -> 2 -> 3
linked_list.delete(2)
linked_list.traverse()  # 输出：1 -> 3

双向链表

在双向链表中，每个节点包含两个引用，一个指向下一个节点，一个指向前一个节点。

定义双向链表节点类

class DoublyListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

基本操作

  1. 初始化链表
  2. 插入节点
  3. 删除节点
  4. 遍历链表
class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        new_node = DoublyListNode(val)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def delete(self, val):
        current = self.head
        if current and current.val == val:
            self.head = current.next
            if self.head:
                self.head.prev = None
            current = None
            return
        while current and current.val != val:
            current = current.next
        if current is None:
            return
        if current.next:
            current.next.prev = current.prev
        if current.prev:
            current.prev.next = current.next
        current = None

    def traverse_forward(self):
        current = self.head
        while current:
            print(current.val, end=" -> " if current.next else "\n")
            current = current.next

    def traverse_backward(self):
        current = self.head
        if not current:
            return
        while current.next:
            current = current.next
        while current:
            print(current.val, end=" -> " if current.prev else "\n")
            current = current.prev

# 示例
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(1)
doubly_linked_list.append(2)
doubly_linked_list.append(3)
doubly_linked_list.traverse_forward()  # 输出：1 -> 2 -> 3
doubly_linked_list.delete(2)
doubly_linked_list.traverse_forward()  # 输出：1 -> 3
doubly_linked_list.traverse_backward()  # 输出：3 -> 1

循环链表

在循环链表中，最后一个节点的 next 引用指向头节点，形成一个循环。可以是单向的也可以是双向的。

单向循环链表节点类和基本操作

class CircularListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        new_node = CircularListNode(val)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        last = self.head
        while last.next != self.head:
            last = last.next
        last.next = new_node
        new_node.next = self.head

    def traverse(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.val, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(head)")

# 示例
circular_linked_list = CircularLinkedList()
circular_linked_list.append(1)
circular_linked_list.append(2)
circular_linked_list.append(3)
circular_linked_list.traverse()  # 输出：1 -> 2 -> 3 -> (head)

标签：current,head,val,题解,self,链表,next,力扣,两数
From： https://www.cnblogs.com/yukihan/p/18330652

相关文章

  • curl发送get和post请求时遇到&截断的问题解决
    get的parameter里带&被截断处理第一种是双引号括住 第二种是加反斜杠转义 post请求的body里有参数的value带了&curl-XPOSThttp://qa-ci.fuxi.netease.com:36800/job/xxxxx/xxxx--userxxxx:xxxxx-d token=popo -d"msg=cd/ssd/deployment_bash&&bashkill.b......
  • P10812 【MX-S2-T3】跳 题解
    题目分析考虑DP。显然当没有\(i\)连向\(i+1\)的边时，整个图是一个DAG，可以直接DP。所以我们DP要解决的唯一问题，就是考虑上\(i\)到\(i+1\)的边。考虑从\(n\)走到\(1\)的过程。当我们从\(i\)向前跳到\(j\)后，此时我们要么向前跳，要么往回走。又因为不能经过重复......
  • CF30E Tricky and Clever Password 题解
    考虑先贪心中间的回文串\(b\)，因为这即使影响了两边的字符串，也不会改变最终的总串长。所以先使用manacher跑出来每个位置的最长回文半径。在考虑怎样找出最长的\(a\)和\(a'\)。可以二分答案，设此时答案为\(k\)，找出的\(b\)串为\(s[l\dotsr]\)，那么其合法的条件就是存在\(......
  • 关于网站安全狗卸载了仍然能拦截的问题解决
    关于网站安全狗卸载了仍然能拦截的问题解决如果你将所有safedog的文件删除的话，可能会导致Apache服务启动不了例如：这里没有提示相关安全狗的信息是因为我已经删除了Apache访问safedog的配置代码，只是提醒错误信息会如上图所示。导致这种原因的结果大概率是因为Apache的conf文件......
  • 题解：P4563 [JXOI2018] 守卫
    思路解法：区间DP。本题虽标上紫题，但黄队说了：“不要被颜色所吓倒。”易得，区间\([l,r]\)中最右端的亭子\(r\)一定会有保镖。先说一下可见性判断吧，只要\(l,r\)的连线的斜率大于\(p,r\)连成的线的斜率大，\(l\)即是可见的。如图，红线是\(r\)无法看到的，而蓝线是\(r\)可......
  • CF1178D Prime Graph 题解
    首先考虑一个问题：如果没有边数是素数的限制，应该怎么构造？这其实很简单，把原图连成一个环即可，每个点度数为\(2\)。接着考虑在原图上加边，注意到\(3\)也是个素数，所以每次可以任意选两个度数为\(2\)的点连边，此时仍然符合条件。这样加边最多可以加\(\left\lfloor\frac{n}{2}\rig......
  • CF685E 题解
    吐槽一下，为啥这道题\(\mathcal{O}(nm)\)可以过。联考的时候做到了这道题，还一直在想更快的算法。。。然后，这联考的数据是自己出的，有\(s=t\)的情况，我反正是完全没有想到，又因为是捆绑测试，直接痛失\(100pts\)。首先考虑转化一下题目。对于一个询问\(l,r,s,t\)，就相当于是让你......
  • P4468[SCOI2007]折纸-题解
    题意：有一个左下角为\((0,0)\)，右上角为\((100,100)\)的正方形，给你\(n\)个有向线段和\(m\)个询问，将纸片依次按直线折叠，然后每次询问让你求出某个点上有多少层纸。分析：观察到数据范围非常小，于是可以直接对于每个询问\(\mathcal{O}(2^n)\)来求。具体的，对于每一个点，倒着枚......
  • P8540 「Wdoi-2」夜空中的 UFO 恋曲 题解
    hanghangakioi考试的时候在乱猜结论，交了几遍就过了，证明当然是赛后才想的（）文中加粗部分是需要读者稍微思考一下原因的地方（不是重点）。先考虑一下样例二，将\(10^{18}\)化成二进制：\(1101...001000000000000000000\)。其实只需要知道末尾有\(18\)个\(0\)就行了，因为在\(x\)......
  • CF1906C Cursed Game 题解
    题目大意交互库有一个\(3\times3\)的01矩阵\(a\)，每次询问一个\(n\timesn\)的01矩阵\(b\)，交互库会返回一个\((n-2)\times(n-2)\)的01矩阵\(c\)，满足：\[c_{x,y}=\bigoplus\limits_{1\lei,j\le3}\left(a_{i,j}\operatorname{AND}b_{x+i-1,y+j-1}\right......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99