LeetCode Algorithm 21. 合并两个有序链表

题目链接：21. 合并两个有序链表

Ideas

算法：归并排序最后Merge
数据结构：链表
思路：这道题考察的就是归并排序最后两个有序链表合并的阶段。首先还是要创建一个空链表res用来表示最终的返回结果。然后对于两个链表的指针，开始分别指向两个链表的第一个元素，然后两个指针往前走，并比较相应位置上元素的大小，取大的那个元素拿到res，以此类推最终直到有一个指针走到相应链表的末尾。最后有可能其中一个指针没有走到链表末尾，那么直接将res的下一个元素指向该指针对应的链表即可。
补充：关于归并排序的具体实现和动画演示可以参考博客：教小学妹学算法：十大经典排序算法深度解析

Code

C++

class Solution {
    
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    
        ListNode* res = new ListNode(-1);
		ListNode* prev = res;
		
		while (list1 != nullptr && list2 != nullptr) {
    
			if (list1->val < list2->val) {
    
				prev->next = list1;
				list1 = list1->next;
			} else {
    
				prev->next = list2;
				list2 = list2->next;
			}
			prev = prev->next;
		}
		
		prev->next = list1 == nullptr ? list2 : list1;
		return res->next;
    }
};