手撕:合并两个有序链表
时间: 2024-09-19 22:00:57 浏览: 6
手撕合并两个有序链表通常是指将两个已排序的单链表合并成一个新的有序链表的过程,而不需要借助额外的数据结构。这可以手动实现,也可以通过编程解决。基本思路是从头开始比较两个链表的节点,将较小的节点添加到新链表中,并递归地对剩下的部分继续操作,直到其中一个链表遍历完。
以下是手动手撕的简单步骤:
1. 创建一个头节点,初始值设为空,用于存储合并后的链表。
2. 比较两个链表的头部节点,将较小的那个节点作为新的链表的头部,并将其后继设置为其原链表的下一个节点。
3. 如果其中有一个链表已经遍历完,则将另一个链表剩余的部分接到结果链表的末尾。
这是一个递归版本的Python伪代码示例:
```python
def merge_sorted_lists(l1, l2):
if not l1: # 如果l1为空,直接返回l2
return l2
elif not l2: # 如果l2为空,直接返回l1
return l1
if l1.val < l2.val: # 将较小节点连接到新链表
l1.next = merge_sorted_lists(l1.next, l2)
return l1
else:
l2.next = merge_sorted_lists(l1, l2.next)
return l2
```
相关问题
c语言合并两个有序链表
在C语言中,合并两个有序链表通常意味着将两个已经排序好的链表合并成一个新的有序链表。合并过程遵循排序的规则,即在新链表中的任一节点都应该是两个输入链表中相应位置节点的最小值。
实现合并的步骤大致如下:
1. 创建一个新链表的头节点,它将作为合并后链表的起始点。
2. 设置两个指针分别指向两个原始链表的头节点。
3. 比较两个指针指向的节点,将较小值的节点链接到新链表的末尾,并移动指向较小值节点的指针到下一个节点。
4. 重复步骤3,直到其中一个链表遍历完成。
5. 如果其中一个链表已经全部连接到新链表中,将另一个链表剩余的部分直接连接到新链表的末尾。
6. 最终,新链表的头节点的下一个节点即为合并后链表的起始节点。
下面是实现这一过程的伪代码示例:
```c
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 创建一个哑节点,它的 next 指针将指向合并后链表的头节点
struct ListNode dummy;
dummy.next = NULL;
struct ListNode *tail = &dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 直接连接剩余部分
if (l1 != NULL) {
tail->next = l1;
} else {
tail->next = l2;
}
// 返回合并后的链表的头节点
return dummy.next;
}
```
在这个例子中,`ListNode` 是链表节点的结构体定义,它至少包含一个整数字段 `val` 和一个指向下一个 `ListNode` 的指针 `next`。
力扣合并两个有序链表
要合并两个有序链表,可以使用递归或迭代的方式。
以下是使用迭代的方法:
```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
```
这个方法的时间复杂度是 O(n + m),其中 n 和 m 分别是两个链表的长度。
希望对你有帮助!如果有任何其他问题,请随时问我。