合并两个有序链表

---

题目链接

https://leetcode.cn/problems/merge-two-sorted-lists/

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

思路分析

（1）首先考虑空链表的处理

（2）确定头节点，谁小谁做头

（3）通过两个指针遍历链表，依次比较节点大小，链接节点

（4）最后链接剩余节点

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 考虑空链表
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }

        // 确定头节点，谁小谁做头
        ListNode head = list1.val <= list2.val ? list1 : list2;

        // 定义两个指针遍历
        ListNode cur1 = head.next;
        // cur 指向不是 head 为头的链表
        ListNode cur2 = head == list1 ? list2 : list1;

        // 定义一个指针用于挂接下一个节点，头指针不动
        ListNode pre = head;

        while (cur1 != null && cur2 != null) {
            // 确定挂接节点
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            // pre 移动到新挂接的节点处，准备挂接下一个节点
            pre = pre.next;
        }

        // 挂接剩余节点
        pre.next = cur1 == null ? cur2 : cur1;

        return head;
    }
}