将单链表中相邻的两个元素合并,数据域相加,用算法编写代码
时间: 2024-09-25 13:01:38 浏览: 28
数据结构 第2章 线性表.ppt
这是一个简单的链表操作问题,可以使用迭代或递归的方式解决。以下是使用Python编写的迭代解决方案:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def mergeTwoLists(l1, l2):
# 创建一个新的头节点
dummy_head = ListNode(0)
current = dummy_head
while l1 and l2:
# 将l1和l2的当前节点值相加,然后将结果作为新节点的值
sum_val = l1.val + l2.val
new_node = ListNode(sum_val)
# 更新指针,指向下一个需要合并的节点
current.next = new_node
current = current.next
# 移动l1和l2的指针,直到其中一个链表结束
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
# 如果有一个链表还有剩余元素,直接将其连接到新链表的末尾
if l1:
current.next = l1
elif l2:
current.next = l2
return dummy_head.next
```
在这个代码中,我们首先创建一个虚拟头节点`dummy_head`,然后遍历两个链表,每次都把两个节点的值相加形成新的节点,接着移动指针到下一个位置。当一个链表遍历完,我们将另一个链表剩下的部分直接接到新链表的末尾。
阅读全文