首页将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。c语言

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。c语言

时间: 2023-10-19 12:08:00 浏览: 112

我可以帮你解决这个问题。这个问题可以通过遍历两个链表，比较节点大小，将较小节点的指针连接到新链表上，并将对应链表的指针移动到下一个节点，直到其中一个链表为空。最后将另一个链表的剩余节点连接到新链表上即可。以下是代码示例： ```c /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ struct ListNode dummy = {0}; struct 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; } ``` 这是一个时间复杂度为 $O(n)$，空间复杂度为 $O(1)$ 的算法。

阅读全文