【一刷《剑指Offer》】面试题 17：合并两个排序的链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //不考虑头结点(其实考虑头结点更简单，这里按照难的来)
        //合并前，先判定
        if(list1==nullptr) return list2;
        if(list2==nullptr) return list1;
 
        //合并无非是比较各自首节点谁小，就把该节点从原链表中删除，再尾插到新节点处，比较时两个链表任何一个都不能为空
        ListNode* newHead=nullptr;
        ListNode* end=nullptr;
        while(list1 && list2)
        {
            ListNode* cur=nullptr;
 
            //先判定拿那个节点
            if(list1->val<list2->val) cur=list1;
            else cur=list2;
 
            //再在指定链表中，删除目标节点
            if(cur==list1) list1=list1->next;
            else list2=list2->next;
 
            //尾插到新链表,这里要考虑第一次插入的情况
            if(newHead==nullptr)
            {
                newHead=cur;
                end=cur;
            }
            else
            {
                end->next=cur;
                end=end->next;
            }
        }
 
        //合并后可能会有几种情况：1.pHead1为空 2.pHead2为空 3.都为空(合并完成)
        if(list1) end->next=list1;
        if(list2) end->next=list2;
        return newHead;
    }
};

//写法一
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr) return list2;
        if(list2==nullptr) return list1;
        if(list1->val<=list2->val)
        {
            list1->next=mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};
 
//写法二
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr) return list2;
        if(list2==nullptr) return list1;
        ListNode* newHead=nullptr;
        if(list1->val<=list2->val)
        {
            newHead=list1;
            list1=list1->next;
        }
        else
        {
            newHead=list2;
            list2=list2->next;
        }
        newHead->next=mergeTwoLists(list1, list2);
        return newHead;
    }
};