c++实现合并两个有序链表

leetcode题目：力扣

执行结果：

 代码实现：

/**
 * 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;
        else if(list2==nullptr)
            return list1;
        ListNode* res,*small,*big,*temp;
        if(list1->val>=list2->val)
        {
            res=list2;
            big=list1;
        }
            
        else
        {
            res=list1;
            big=list2;
        }
    small=res;
    while(small->next!=nullptr)
    {
        if(small->next->val<=big->val)
        {
            small=small->next;
        }
        
        else
        {//当前small-val<=big->val并且small->next->val>big->val
            temp=small->next;
            small->next=big;
            small=temp;
            while(big->next!=nullptr)
            {
                if(big->next->val<=small->val)
                {
                    big=big->next;
                }
                else
                {
                    temp=big->next;
                    big->next=small;
                    big=temp;
                    break;
                }
            }
            if(big->next==nullptr&&big->val<=small->val)
            {
                big->next=small;
                return res;
            }
            
        }
    }
    //如果执行到此，说明small的长度小于big
    small->next=big;
    return res;
    }
};

对比看了一下别人的题解，代码更简单，但是执行时间相对较多。

题解:

先对特殊情况进行判断。而后，得到第一个节点值较小的链表，用res保存其头指针，res将作为结果链表的指针。small指向第一个节点值较小的链表，遍历small，直到到达某一个节点：满足该加点的值小于big指向的节点值，并且该节点的下一个节点值大于big指向的节点值，说明此时small节点应当指向big节点，执行temp=small->next;small->next=big；small=temp。接着遍历big，直到找到一个节点，该节点的值小于small节点的下一个节点，并且该节点的下一个节点值大于small节点值。

while循环中条件：当下一个节点为空时，说明当前节点已经是最后一个节点。对于small来说，如果退出了while（small->next!=nullptr）循环，说明当前small节点已经是最后一个节点，并且仍然小于big节点。对于while(big->next!=nullptr)，该循环退出有些不同，存在两种情况，需要进行判断。