一、题目

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

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

二、题目分析

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

 1#!/usr/bin/env python
 2# coding=utf8
 3# ===============================================================================
 4#   Copyright (C) 2018 www.361way.com site All rights reserved.
 5#
 6#   Filename      ：02.py
 7#   Author        ：yangbk <itybku>
 8#   Create Time   ：2018-08-16 19:00
 9#   Description   ：
10# ===============================================================================
11l1 = [2,4,3]
12l2 = [5,6,4]
13def addstr(l):
14  a = ''
15  for i in l:
16    i = str(i)
17    a = a + i
18  return a
19n1 = addstr(l1)
20n2 = addstr(l2)
21n3 = int(n1) + int(n2)
22print n1,n2,n3
23print  list(''.join(str(n3)[::-1]))
24[root@localhost leetcode]# python 02.py
25243 564 807
26['7', '0', '8']

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

三、链表（Linked lists）

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

linked lists
linked lists

单向链表很简单，链表的创建就是添加结点到链表的最后，开始是添加一个结点到head结点后面，然后添加一个结点到上次添加的结点后面，每次新建的结点的指针总是指向NULL指针。更多链表相关内部可以参考：

四、功能实现

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

 1class Solution(object):
 2    def addTwoNumbers(self, l1, l2):
 3        """
 4        :type l1: ListNode
 5        :type l2: ListNode
 6        :rtype: ListNode
 7        """
 8        nHead, flag = ListNode(0), 0
 9        head = nHead
10        while flag or l1 or l2:
11            node = ListNode(flag)
12            if l1:
13                print node.val
14                node.val += l1.val
15                print node.val
16                print '---------'
17                l1 = l1.next
18            if l2:
19                node.val += l2.val
20                l2 = l2.next
21            print node.val
22            print '***********'
23            flag = node.val // 10
24            node.val %= 10
25            print flag,node.val
26            print '========'
27            head.next, head = node, node
28        return nHead.next

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

listnode
listnode

如何反向逆转代码如下：

 1class ListNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.next = None
 5def reverse(head):
 6    if head is None or head.next is None:
 7        return head
 8    pre = None
 9    cur = head
10    h = head
11    while cur:
12        h = cur
13        tmp = cur.next
14        cur.next = pre
15        pre = cur
16        cur = tmp
17    return h
18class Solution(object):
19    def addTwoNumbers(self, l1, l2):
20        newl1=reverse(l1)
21        newl2=reverse(l2)
22        nHead, flag = ListNode(0), 0
23        head = nHead
24        while newl1 or newl2 or flag:
25            node = ListNode(flag)
26            if newl1:
27                node.val += newl1.val
28                newl1 = newl1.next
29            if l2:
30                node.val += newl2.val
31                newl2 = newl2.next
32            flag = node.val // 10
33            node.val %= 10
34            head.next, head = node, node
35        newHead = reverse(nHead)
36        print newHead.val
37        print newHead.next.val
38        print newHead.next.next.val
39l1 = ListNode(2)
40l1.next = ListNode(4)
41l1.next.next = ListNode(3)
42l2 = ListNode(5)
43l2.next = ListNode(6)
44l2.next.next = ListNode(4)
45p = Solution()
46p.addTwoNumbers(l1, l2)

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