两个递增的有序链表合并为一个递增的有序链表
时间: 2023-09-12 10:02:45 浏览: 135
算法思路:
1. 定义一个新的链表作为合并后的链表,同时定义一个指针用于遍历新链表;
2. 比较两个链表的头结点,将较小的节点接入新链表,并将指针指向该节点;
3. 循环比较两个链表的头结点,将较小的节点接入新链表,并将指针指向该节点,直到其中一个链表为空;
4. 将另一个链表剩余的节点直接接到新链表的尾部;
5. 返回新链表的头结点。
Python 代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
# 定义新链表和指针
head = ListNode()
cur = head
# 比较两个链表的头结点
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
# 将另一个链表剩余的节点直接接到新链表的尾部
if l1:
cur.next = l1
if l2:
cur.next = l2
# 返回新链表的头结点
return head.next
```