将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用个链表的存储空间,不另外占用其他的存储空间。表中允许有重复的数据。算法代码是
时间: 2024-11-21 13:30:52 浏览: 18
将两个非递减的有序链表合并成一个非递增的有序链表,可以采用双指针法。首先,我们需要创建一个新的链表头节点,然后设置两个指针,分别指向两个输入链表的头部。接下来,比较这两个指针所指的元素,选择较小的那个添加到新链表,并移动对应的指针。当其中一个链表遍历完之后,只需将另一个链表剩余的部分依次添加到新链表即可。
这是一个简单的Python代码示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
# 创建新链表头节点
dummy = ListNode(0)
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
# 如果其中一个链表还有剩余,将其余部分添加到新链表
if l1:
tail.next = l1
elif l2:
tail.next = l2
return dummy.next
```
阅读全文