最简单粗暴的想法是将两个链表的所有元素拿出来放在一个数组中,再将此数组排序,最后生成一个新链表并返回。由于给出的参数本身就是两个排好序的链表,可以进行一次遍历,就能保证元素仍然是有序的:每次比较当前指针指向的两个元素的大小,较小的拿出来作为当前元素并将指针向前移动一个位置,然后继续比较下一个元素。对于内存的使用也可以优化,可以直接复用当前链表的结点,仅仅调整结点之间指针的指向即可。
// C++
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr) {
return list2;
}
if (list2 == nullptr) {
return list1;
}
ListNode* head = new ListNode();
ListNode* p = head;
ListNode *p1 = list1, *p2 = list2;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val < p2->val) {
p->next = p1;
p1 = p1->next;
p = p->next;
} else {
p->next = p2;
p2 = p2->next;
p = p->next;
}
}
if (p1 != nullptr) {
p->next = p1;
}
if (p2 != nullptr) {
p->next = p2;
}
return head->next;
}
};
标签:p2,p1,ListNode,21,nullptr,next,链表,Hot
From: https://www.cnblogs.com/louistang0524/p/18435248