Python 两数相加 Leetcode No.2
思路很简单，模拟小学加法运算就好了，因为是逆序的，头指针指向的那个其实就是个位，往后加就完事，但是唯一需要注意的是，最高位可能有进位。（属于代码练习题）
ps：还有人说先把数全部取出来，用计算机加法算完，再建立链表连接起来，乍一看有点投机取巧好像可行的样子，但是我们要考虑计算和的时候会溢出。
还有人考虑直接在原来的链表上改数字，多一位的话，就再加一个链表，首先不知道leetcode允不允许改数字，毕竟这种题目也是考察你的链表能力，其次就算可以改，也没那个必要，毕竟就算少个几百个节点，问题也不大就是了。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
(
object
)
:
def
addTwoNumbers
(
self
,
l1
,
l2
)
:
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
#进位
add
=
0
#这是两个头节点
l3
=
l4
=
ListNode
(
0
)
while
True
:
#算节点的和
if
l1
or
l2
:
if
l1
:
sum
=
l1
.
val
+
add
if
l2
:
sum
+=
l2
.
val
elif
l2
:
sum
=
l2
.
val
+
add
if
l1
:
sum
+=
l1
.
val
else
:
sum
=
add
add
=
0
#判断是否给add赋值
if
sum
//
10
>
0
:
add
=
1
sum
%=
10
#为新节点赋值
l3
.
val
=
sum
l1
=
l1
.
next
if
l1
else
l1
l2
=
l2
.
next
if
l2
else
l2
#创建新的链表
if
l1
or
l2
or
add
:
l3
.
next
=
ListNode
(
0
)
l3
=
l3
.
next
else
:
break
return
l4
ps：分享很多国外人写的代码，就感觉卧槽，还可以这么写，思路大家都一样，写法会有很多不同哦
#第一个老外写的，用了str
class
Solution
:
def
addTwoNumbers
(
self
,
l1
,
l2
)
:
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
str_l1
,
str_l2
=
''
,
''
while
l1
:
str_l1
+=
str
(
l1
.
val
)
l1
=
l1
.
next
while
l2
:
str_l2
+=
str
(
l2
.
val
)
l2
=
l2
.
next
int_l1
=
int
(
str_l1
[
:
:
-
1
]
)
int_l2
=
int
(
str_l2
[
:
:
-
1
]
)
return
list
(
map
(
int
,
str
(
int_l1
+
int_l2
)
[
:
:
-
1
]
)
)
#第二个老外写的，用了divmod，有点意思哈
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
(
object
)
:
def
addTwoNumbers
(
self
,
l1
,
l2
)
:
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
result
=
ListNode
(
0
)
result_tail
=
result
carry
=
0
while
l1
or
l2
or
carry
:
val1
=
(
l1
.
val
if
l1
else
0
)
val2
=
(
l2
.
val
if
l2
else
0
)
carry
,
out
=
divmod
(
val1
+
val2
+
carry
,
10
)
result_tail
.
next
=
ListNode
(
out
)
result_tail
=
result_tail
.
next
l1
=
(
l1
.
next
if
l1
else
None
)
l2
=
(
l2
.
next
if
l2
else
None
)
return
result
.
next
#第三个老外用了递归写的，可以看看
# Definition for singly-linked list.
class
ListNode
(
object
)
:
def
__init__
(
self
,
x
)
:
self
.
val
=
x
self
.
next
=
None
def
printList
(
nodeStart
)
:
print
(
nodeStart
.
val
)
if
nodeStart
.
next
==
None
:
return
else
:
printList
(
nodeStart
.
next
)
class
Solution
(
object
)
:
def
addTwoNumbers
(
self
,
l1
,
l2
)
:
if
l1
==
None
:
return
l2
if
l2
==
None
:
return
l1
sval
=
l1
.
val
+
l2
.
val
if
sval
<
10
:
ansNode
=
ListNode
(
sval
)
ansNode
.
next
=
self
.
addTwoNumbers
(
l1
.
next
,
l2
.
next
)
return
ansNode
else
:
rval
=
l1
.
val
+
l2
.
val
-
10
ansNode
=
ListNode
(
rval
)
ansNode
.
next
=
self
.
addTwoNumbers
(
ListNode
(
1
)
,
self
.
addTwoNumbers
(
l1
.
next
,
l2
.
next
)
)
return
ansNode
