已知两个带头结点的单链表中结点值均由小到大有序,设计一个算法,利用两个表原来的结点空间将它们合并成一个表,使合并后的结点值仍然有序。
时间: 2023-04-10 12:03:43 浏览: 64
可以使用双指针法,分别指向两个链表的头结点,比较两个指针所指结点的值,将较小的结点加入新的链表中,然后将指针后移,直到其中一个链表为空,将另一个链表剩余的结点加入新的链表中即可。时间复杂度为 O(m+n),其中 m 和 n 分别为两个链表的长度。以下是示例代码:
```
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
```
相关问题
已知一个递增有序的不带头结点的单链表,设计算法从该链表删除与给定值相等的所有元素
可以回答这个问题。算法如下:
1. 定义两个指针,分别指向当前节点和前一个节点。
2. 遍历链表,如果当前节点的值等于给定值,则删除该节点。
3. 如果当前节点的值不等于给定值,则将前一个节点指向当前节点。
4. 遍历完整个链表后,返回链表头节点。
具体实现可以参考以下代码:
struct ListNode* deleteNode(struct ListNode* head, int val) {
struct ListNode *prev = NULL, *curr = head;
while (curr != NULL) {
if (curr->val == val) {
if (prev == NULL) {
head = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
curr = prev == NULL ? head : prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
return head;
}
已知带头结点单链表L中存储一组整数,编写算法删除表中所有值大于x的结点。
以下是删除表中所有值大于x的结点的算法:
```
void deleteNodesGreaterThanX(ListNode* head, int x) {
ListNode* current = head->next;
ListNode* previous = head;
while (current != nullptr) {
if (current->val > x) {
previous->next = current->next;
delete current;
current = previous->next;
} else {
previous = current;
current = current->next;
}
}
}
```
其中,ListNode 是单链表的结点类型,head 是头结点,val 是结点存储的整数值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)