算法|【Python】【LeetCode】【2.两数相加】【链表】算法|链表

文章目录

0.链表
1.原文题目
2.解题思路
3.Python代码

0.链表
刚刚看到第二题，一脸懵的！！Python中的链表从来没接触过，数据结构的中链表好像也忘得差不多了，于是百度Google动起来，在这里推荐比较好的单链表讲解！！对链表的知识了解有限，似懂非懂，有弄错的地方希望指出。

链表(linked list)是由一组被称为结点的数据元素组成的数据结构，每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址信息，所以用一个变量就能够访问整个结点序列。也就是说，结点包含两部分信息：一部分用于存储数据元素的值，称为信息域；另一部分用于存储下一个数据元素地址的指针，称为指针域。链表中的第一个结点的地址存储在一个单独的结点中，称为头结点或首结点。链表中的最后一个结点没有后继元素，其指针域为空。

1.原文题目

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

2.解题思路
处理关键问题

【算法|【Python】【LeetCode】【2.两数相加】【链表】】一位数和一位数相加，大于 10 时候，除以 10，商为进位数，余数为该位的数。时间复杂度：O(n)

三种类型	说明
L1=[0]; L2=[0,1]	两个链表长度不一样
L1=[]; L2=[0,1]	有一个链表为空
L1=[5,5]; L2=[4,5]	总和还能向前进位

3.Python代码

# -*- coding: utf-8 -*- # @Time : 2019/5/12 12:40 # @Author : ZXL # @Site : # @File : 2.两数相加.py # @Software: PyCharm# 单链表的定义 # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def addTwoNumbers(self, l1, l2): if l1 is None: return l2 elif l2 is None: return l1 else: carry = 0 ret = ListNode(0) ret_Last = ret while (l1 or l2): sum = 0 if l1: sum += l1.val l1 = l1.next if l2: sum += l2.val l2 = l2.next sum += carry ret_Last.next = ListNode(sum % 10) ret_Last = ret_Last.next carry = (sum >= 10) ret = ret.next if carry: ret_Last.next = ListNode(1) del ret_Last return retdef myPrintList(l): while (True): print(l.val) if l.next is not None: l = l.next else: print() breakif __name__ == '__main__': # 342 + 465 = 807 l1_1 = ListNode(3) l1_2 = ListNode(4) l1_3 = ListNode(2) l1_1.next = l1_2 l1_2.next = l1_3l2_1 = ListNode(4) l2_2 = ListNode(6) l2_3 = ListNode(5) l2_1.next = l2_2 l2_2.next = l2_3l3 = Solution().addTwoNumbers(l1_1, l2_1) myPrintList(l3)