pta有序链表合并Python
时间: 2024-09-28 13:02:31 浏览: 18
在Python中,合并两个已排序的链表(也称为“pta”或“平行链表”)通常涉及遍历每个列表并将它们按顺序连接起来。这里是一个简单的递归函数示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
if not l1: # 如果l1为空,则直接返回l2
return l2
elif not l2: # 如果l2为空,则直接返回l1
return l1
else: # 否则,比较当前节点值并选择较小的那个作为结果的新节点
if l1.val < l2.val:
result = l1 # 将l1的头节点加入结果
l1 = l1.next # 移动l1指针到下一个节点
else:
result = l2
l2 = l2.next
result.next = merge_sorted_lists(l1, l2) # 递归处理剩余部分
return result
```
这个函数会创建一个新的链表,其中包含两个输入链表的所有元素,但按照升序排列。
相关问题
有序链表合并
链表合并是指将两个有序链表合并成一个有序链表。可以通过递归的方式实现,具体步骤如下:
1. 如果两个链表中有一个为空,直接返回另一个链表。
2. 比较两个链表的头结点,将较小值的结点作为合并后链表的头结点。
3. 递归调用合并函数,将较小值结点的 next 指针指向递归调用返回的链表的头结点。
4. 返回合并后的链表。
以下是示例代码实现:
```
#include <iostream>
using namespace std;
// 链表结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x): val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
int main() {
// 构造链表1: 1->2->4
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(2);
l1->next->next = new ListNode(4);
// 构造链表2: 1->3->4
ListNode* l2 = new ListNode(1);
l2->next = new ListNode(3);
l2->next->next = new ListNode(4);
// 合并链表
ListNode* l3 = mergeTwoLists(l1, l2);
// 打印输出合并后的链表: 1->1->2->3->4->4
while (l3 != NULL) {
cout << l3->val << " ";
l3 = l3->next;
}
return 0;
}
```
6-2 有序链表合并
链表是一种常见的数据结构,它可以用来存储一系列的元素,每个元素都包含一个指向下一个元素的指针。有序链表是指链表中的元素按照某个规则排列,比如按照大小顺序排列。
有序链表合并是指将两个有序链表合并成一个有序链表。具体的合并过程可以使用迭代或递归的方式实现。
下面是一个使用迭代方式实现的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
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
if l1:
curr.next = l1
if l2:
curr.next = l2
return dummy.next
```
在这个示例代码中,我们定义了一个 `ListNode` 类来表示链表中的每个元素,其中包含一个 `val` 属性和一个 `next` 属性,分别表示元素的值和指向下一个元素的指针。
然后我们定义了一个 `mergeTwoLists` 函数,它接受两个有序链表作为参数,并返回一个合并后的有序链表。在函数中,我们创建了一个 `dummy` 节点作为合并后链表的头节点,然后使用 `curr` 变量来记录合并后链表的当前节点。
接着我们使用一个 `while` 循环来遍历两个输入链表,对于每个节点,我们将其值较小的节点添加到合并后链表的末尾,并将该链表的指针后移。最后,我们判断是否存在某个链表还有剩余节点,如果有,则将剩余节点直接添加到合并后链表的末尾。
最后我们返回合并后链表的头节点即可。