建立两个非递减有序单向链表,然后合并成一个非递增链表。
时间: 2023-06-09 18:07:36 浏览: 100
可以使用归并排序的思想来解决这个问题。首先将两个链表分别排序,然后从头开始比较两个链表的节点,将较小的节点插入到结果链表中,直到其中一个链表为空。最后将剩余的节点加入到结果链表尾部即可。
具体实现细节可以参考以下代码:
```
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
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;
if (l2 != NULL) tail->next = l2;
ListNode* prev = NULL;
ListNode* curr = dummy.next;
while (curr != NULL) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* fast = head->next;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
ListNode* head2 = slow->next;
slow->next = NULL;
ListNode* l1 = sortList(head);
ListNode* l2 = sortList(head2);
return mergeTwoLists(l1, l2);
}
```
排序后,我们需要将结果链表反转一下,才能得到非递增链表。