合并两个有序链表

MergeTwoLists

1,初始时,合并的链表 preHead 为空

1
2
3


        ListNode* preHead = new ListNode(0);

        ListNode* prev = preHead;

2,设定边界,比较 l1与节点的值,若l1 的值小于于 l2的值则 pre的 next 指针指向 l1,更新 l1 的位置为l2的 next指针指向的位置,否则将 prev 的 next 指针指向 l2，并将 l2 的位置更新为 l2 的下一个节点,将 l1,l2视为一个节点而不是链表

‍

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

3,此时，l2 已经为空，因此直接将 l1 的剩余部分连接到 prev 上。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


    	// 处理剩余节点： 若其中一个链表已经遍历完毕，则直接将另一个链表的剩余部分连接到 prev 上
        prev->next = l1 == nullptr ? l2 : l1;
    	// 这行代码的逻辑可以理解为：
        if (l1 != nullptr) {
        	prev->next = l1;
    	}
    	if (l2 != nullptr) {
        	prev->next = l2;
    	}

		# 返回指向合并后链表的第一个节点的指针，以完成合并两个有序链表的函数，并将合并后链表的头节点返回供调用者使用
        return preHead->next;

‍