题目描述：

LeetCode 445. Add Two Numbers II

You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

```Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 8 -> 0 -> 7```

解题思路：

```1. 统计两链表长度s1, s2；最终结果链表长度s = max(s1, s2) （若有进位，则为s+1）

2. 将两链表对齐并逐节点求和，记头节点为h（头节点为dummy node，最高位从h.next开始）

3. 初始令指针p指向头节点h，执行循环：

令指针q = p.next，重复向其下一节点移动，直到q为空或者q.val ≠ 9

如果q.val ＞ 9，说明p与q之间的所有节点需要进位，令p向q移动同时修改p.val

否则，令p = q```

Python代码：

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
s1 = self.getSize(l1)
s2 = self.getSize(l2)
s = max(s1, s2)

p = h = ListNode(0)
while s:
p.next = ListNode(0)
p = p.next
if s <= s1:
p.val += l1.val
l1 = l1.next
if s <= s2:
p.val += l2.val
l2 = l2.next
s -= 1

p = h
while p:
q = p.next
while q and q.val == 9:
q = q.next
if q and q.val > 9:
while p != q:
p.val += 1
p = p.next
p.val -= 10
else: p = q
return h if h.val else h.next

def getSize(self, h):
c = 0
while h:
c += 1
h = h.next
return c
``````

Pingbacks已关闭。