leetcode02两数相加

一、题目

给定两个<strong>非空链表</strong>来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。示例：



<br />

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

二、题目分析

最初的并未看清链表的提示。只是将其当成一个数组来处理了，按数组的思想处理的代码和执行结果如下：



<br />

#!/usr/bin/env python
# coding=utf8
# ===============================================================================
#   Copyright (C) 2018 www.361way.com site All rights reserved.
#
#   Filename      ：02.py
#   Author        ：yangbk 
#   Create Time   ：2018-08-16 19:00
#   Description   ：
# ===============================================================================
l1 = [2,4,3]
l2 = [5,6,4]
def addstr(l):
  a = ''
  for i in l:
    i = str(i)
    a = a + i
  return a
n1 = addstr(l1)
n2 = addstr(l2)
n3 = int(n1) + int(n2)
print n1,n2,n3
print  list(''.join(str(n3)[::-1]))
[root@localhost leetcode]# python 02.py
243 564 807
['7', '0', '8']

不过将代码提交后，不通过。

三、链表（Linked lists）

上面题目提到了一个非常有用的概念链表，其一般只存在于更底层的高级语言中，如C、JAVA、Golang等。其一般都是和指针相关的。而且上面提到的是单向链表，这里就截图一个C++实现的单向链表的示意图：



<img src="https://www.361way.com/wp-content/uploads/2018/08/linkedlists.png" width="502" height="248" title="linked lists" alt="linked lists" />



单向链表很简单，链表的创建就是添加结点到链表的最后，开始是添加一个结点到head结点后面，然后添加一个结点到上次添加的结点后面，每次新建的结点的指针总是指向NULL指针。



更多链表相关内部可以参考：



<a href="https://www.jianshu.com/p/c78c70c92a6c" target="_blank" rel="noopener">链表</a>



<a href="https://blog.csdn.net/fisherwan/article/details/25796625" target="_blank" rel="noopener">链表（单向、双向、单向循环、双向循环）学习过程总结</a>



<a href="https://blog.csdn.net/mianhuantang848989/article/details/72393561?locationNum=8&fps=1" target="_blank" rel="noopener">C语言通用双向循环链表操作函数集</a>



<a href="http://www.cnblogs.com/yupeng/p/3413763.html" target="_blank" rel="noopener">python 数据结构之单链表的实现</a>

四、功能实现

对位相加，设置进位位，重点在于如何写单链表。其代码如下：



<br />

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        nHead, flag = ListNode(0), 0
        head = nHead
        while flag or l1 or l2:
            node = ListNode(flag)
            if l1:
                print node.val
                node.val += l1.val
                print node.val
                print '---------'
                l1 = l1.next
            if l2:
                node.val += l2.val
                l2 = l2.next
            print node.val
            print '***********'
            flag = node.val // 10
            node.val %= 10
            print flag,node.val
            print '========'
            head.next, head = node, node
        return nHead.next

上面加了很多print代码，主要方便打印相关信息。实际执行的时候并不需要。上面的代码只是做了进位处理，并没有反转操作。实现执行的时候打印出来结果如下：



<img src="https://www.361way.com/wp-content/uploads/2018/08/listnode.png" width="596" height="547" title="listnode" alt="listnode" />



如何反向逆转代码如下：



<br />

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
def reverse(head):
    if head is None or head.next is None:
        return head
    pre = None
    cur = head
    h = head
    while cur:
        h = cur
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return h
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        newl1=reverse(l1)
        newl2=reverse(l2)
        nHead, flag = ListNode(0), 0
        head = nHead
        while newl1 or newl2 or flag:
            node = ListNode(flag)
            if newl1:
                node.val += newl1.val
                newl1 = newl1.next
            if l2:
                node.val += newl2.val
                newl2 = newl2.next
            flag = node.val // 10
            node.val %= 10
            head.next, head = node, node
        newHead = reverse(nHead)
        print newHead.val
        print newHead.next.val
        print newHead.next.next.val
l1 = ListNode(2)
l1.next = ListNode(4)
l1.next.next = ListNode(3)
l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)
p = Solution()
p.addTwoNumbers(l1, l2)

上面的关于链表部分的代码不是我写的，来自互联网。因为python里不存在指针的概念。而且之前在使用python的时候也从没有关系过链表，其对链表的实现不同于其他高级语言。