链表相加（链表实现两数相加）

链表相加是一种常见的算法题目，通常出现在面试中。在这个问题中，我们需要两个非负整数用链表的形式表示，然后将它们相加并返回结果。本文将详细介绍链表相加的实现原理和步骤。

## 实现原理

链表相加的实现原理主要是模拟手算加法的过程。我们从两个链表的头部开始遍历，每次将对应节点的值相加并保存进位。当遍历完成后，我们就可以得到相加的结果。

## 算法步骤

1. 定义一个新的链表用于存储相加的结果。

2. 初始化进位为0，并用两个指针分别指向两个链表的头部。

3. 遍历两个链表，同时将对应节点的值相加并加上进位。

4. 将相加结果的个位数作为新节点的值，并更新进位。

5. 如果有一个链表遍历完毕，而另一个链表还有剩余节点，则继续将剩余节点的值加上进位。

6. 如果最高位有进位，需要添加一个值为1的新节点。

7. 返回新链表的头部作为相加的结果。

## 代码实现

以下是链表相加的Python实现代码：

```python

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next = next

def addTwoNumbers(l1, l2):

dummy = ListNode(0)

curr = dummy

carry = 0

while l1 or l2:

x = l1.val if l1 else 0

y = l2.val if l2 else 0

sum = x + y + carry

carry = sum // 10

curr.next = ListNode(sum % 10)

curr = curr.next

if l1: l1 = l1.next

if l2: l2 = l2.next

if carry:

curr.next = ListNode(1)

return dummy.next

```

## 总结

通过上述算法步骤和代码实现，我们可以轻松地实现链表相加的功能。这个问题虽然看似简单，但涉及到链表的遍历和基本的加法运算，对于理解链表的操作和算法设计有着重要的意义。在实际工程中，我们还可以根据具体需求对算法进行优化，例如提前判断链表是否为空或者采用递归的方式实现相加操作。链表相加是一个很好的练习题目，也可以帮助我们提高对链表和算法的理解和熟练度。