力扣 hot100 Day30

21. 合并两个有序链表

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

//自己写的
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) return list2;
        else if(list2 == nullptr) return list1;   
        ListNode * head;
        if(list1->val>=list2->val)
        {
            head = list2;
            list2 = list2->next;
        }
        else
        {
            head = list1;
            list1 = list1->next;
        }
        ListNode * cur = head;        
        while(list1 && list2)
        {
            if(list1->val>=list2->val)
            {
                cur->next=list2;
                list2 = list2->next;               
            }
            else
            {
                cur->next=list1;
                list1 = list1->next;
            }
            cur = cur->next; 
        }
        cur->next = list1 ? list1 : list2;
        return head;
    }
};

逻辑很简单，但这里写的太冗杂了，因为要记录head，需要在head赋值后用cur复制，所以第一次判断不在循环里，很难看。

//ai写的
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);  // 虚拟头节点
        ListNode* tail = &dummy;  // 尾指针，初始指向dummy
        
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        
        // 处理剩余部分
        tail->next = list1 ? list1 : list2;
        
        return dummy.next;  // 返回合并后的头节点
    }
};

这里用一个虚拟头节点，使得逻辑和格式简洁许多，最后返回时也能使用。

//抄的
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

递归法，挺好理解的，适合面试用（估计也很难有简单题）