编写程序实现将两个带头结点的单链表,合并为一个带头结点的单链表,简单易懂的代码
时间: 2024-05-07 09:22:32 浏览: 121
有头结点的单链表表的实现
以下是简单易懂的 Python 代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_lists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next
```
函数 `merge_lists` 接受两个带头结点的单链表 `l1` 和 `l2`,并返回一个合并后的带头结点的单链表。
首先创建一个虚拟头结点 `dummy` 和尾结点 `tail`,初始时它们都指向虚拟头结点。然后,我们遍历 `l1` 和 `l2`,将当前两个链表中较小的结点接到尾结点 `tail` 的后面,并将 `tail` 指向新加入的结点。当其中一个链表遍历完后,我们将另一个链表剩余的结点全部接到尾结点 `tail` 的后面。最后返回虚拟头结点 `dummy` 的下一个结点,即为合并后的链表头结点。
阅读全文