用C++输入两个逆序链表,合并成一个升序链表并输出代码
时间: 2024-10-10 14:02:02 浏览: 30
在C++中,你可以通过遍历两个逆序链表,然后逐个比较节点的值来合并它们形成一个升序链表。以下是合并逆序链表的基本步骤以及示例代码:
首先,定义链表节点结构体:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
```
接下来,我们创建一个函数`mergeTwoLists`来合并两个逆序链表:
```cpp
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
// 如果l1的小于l2,则将l1作为结果链表的一部分,并移动l1到下一个节点
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
// 否则,将l2作为结果链表的一部分,并移动l2到下一个节点
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
```
这个函数递归地比较两个链表当前节点的值,并选择较小的那个插入到新链表中。
最后,可以创建主函数来测试上述函数:
```cpp
void printList(ListNode* head) {
while (head) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
// 创建两个逆序链表示例
ListNode* l1 = new ListNode(40);
ListNode* l2 = new ListNode(20);
l1->next = new ListNode(60);
l2->next = new ListNode(80);
// 合并链表
ListNode* sortedList = mergeTwoLists(l1, l2);
// 输出合并后的升序链表
printList(sortedList);
return 0;
}
```
当你运行此程序时,会输出`20 40 60 80`,这就是合并后形成的升序链表。
阅读全文