建立两个递增有序单向链表,合并为一个递增有序链表
时间: 2024-03-25 18:32:39 浏览: 59
两个递增有序的单链表合并成一个递减有序的.cpp
4星 · 用户满意度95%
以下是两种建立两个递增有序单向链表并合并为一个递增有序链表的方法:
1. 递归方法:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
# 创建链表1
list1 = ListNode(1)
list1.next = ListNode(3)
list1.next.next = ListNode(5)
# 创建链表2
list2 = ListNode(2)
list2.next = ListNode(4)
list2.next.next = ListNode(6)
# 合并链表
merged_list = mergeTwoLists(list1, list2)
# 打印合并后的链表
while merged_list:
print(merged_list.val)
merged_list = merged_list.next
```
2. 迭代方法:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
# 创建链表1
list1 = ListNode(1)
list1.next = ListNode(3)
list1.next.next = ListNode(5)
# 创建链表2
list2 = ListNode(2)
list2.next = ListNode(4)
list2.next.next = ListNode(6)
# 合并链表
merged_list = mergeTwoLists(list1, list2)
# 打印合并后的链表
while merged_list:
print(merged_list.val)
merged_list = merged_list.next
```
阅读全文