已知L1和L2分别指向两个单链表的头结点,且已知其长度分别为m和n。试写一算法将这两个链表连接在一起,请分析你的算法的时间复杂度。
时间: 2024-03-26 07:38:20 浏览: 22
将两个链表连接在一起,实际上就是将 L2 链接到 L1 的末尾。因为已经给出了链表的长度 m 和 n,因此可以先遍历 L1 到其末尾,然后将 L2 连接到 L1 的末尾即可。时间复杂度为 $O(m)$。
下面是算法的具体实现(C++ 代码):
```
ListNode* joinTwoLists(ListNode* L1, ListNode* L2) {
if (L1 == NULL) {
return L2;
}
ListNode* p = L1;
while (p->next != NULL) {
p = p->next;
}
p->next = L2;
return L1;
}
```
其中,ListNode 是链表节点的结构体,包含一个值 val 和一个指向下一个节点的指针 next。L1 和 L2 分别是两个链表的头节点指针。
相关问题
已知两个长度分别为m、n(m、n均大于0)的升序单链表l1和l2,设计一个算法将它们的所有节点合并为一个长度为m+n的降序单链表l。
算法步骤如下:
1. 定义一个新的链表头节点head,以及一个指向head的指针p。
2. 从l1和l2的头节点开始,比较两个节点的值大小,将值较大的节点插入到head节点之后,然后将p指针指向新插入的节点。
3. 重复步骤2,直到l1或l2中的一个链表遍历完毕。
4. 将l1或l2中剩余的节点依次插入到head节点之后,直到两个链表都遍历完毕。
5. 返回head节点的下一个节点,即为合并后的降序单链表l。
代码实现如下:
```
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode();
ListNode* p = head;
while (l1 && l2) {
if (l1->val > l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2;
return head->next;
}
```
已知两个带头节点的单链表l1和l2中的结点值均已按升序排序,设计一个算法,将l1和l2就地合并成一个升序的带头节点单链表,合并之后l1和l2单链表为空,并用l3记录新的带头节点单链表的头指针。
算法步骤如下:
1. 定义三个指针p1、p2、p3,分别指向l1、l2、l3的头节点;
2. 比较p1和p2所指节点的值,将较小值的节点接到p3的后面,并将p3指向新加入的节点;
3. 将p1或p2指向下一个节点,重复步骤2,直到p1或p2为空;
4. 将p1或p2剩余的节点接到p3的后面;
5. 返回l3的头指针。
代码实现如下:
```
ListNode* mergeList(ListNode* l1, ListNode* l2) {
ListNode* p1 = l1->next;
ListNode* p2 = l2->next;
ListNode* p3 = new ListNode(); // 新链表的头节点
ListNode* tail = p3; // 记录新链表的尾节点
while (p1 && p2) {
if (p1->val <= p2->val) {
tail->next = p1;
p1 = p1->next;
} else {
tail->next = p2;
p2 = p2->next;
}
tail = tail->next;
}
if (p1) tail->next = p1;
if (p2) tail->next = p2;
l1->next = nullptr;
l2->next = nullptr;
ListNode* l3 = p3->next;
delete p3;
return l3;
}
```