题解 | #合并有序链表#

遍历l2,将l2的节点加入到l1中，遍历l1做检查，如果l2的val比l1的大则插入到l1的首部（注意到l1已经被改变，所以需要一个变量来保持最终的l1），否则找到l2应该插入到l1的位置，插入即可。应该注意保持链表不会断。

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // write code here
        //遍历l2将其插入到l1中,保证有序;
        if(!l1)
            return l2;
        ListNode* p1 = l1;

        while(l2)
        {
            while(l1)
            {
                if(l2->val >= l1->val)
                {
                    if(l1->next)
                    {
                         if(l2->val <= l1->next->val)
                         {
                             //插入到l1并且保证链表不会断;
                             ListNode* tmp2 = l2->next;
                             ListNode* tmp = l1->next;
                             l1->next = l2;
                             l2->next = tmp;
                             l2 = tmp2;
                             break;
                         }
                    }else
                    {
                        //临时保存l2的下一个节点;
                        ListNode* tmp = l2->next;

                        //直接插入到l1;
                        l1->next = l2;
                        l1 = l1->next;
                        l1->next = NULL;

                        l2 = tmp;
                        break;
                    }
                }
                else
                {
                    //l2的val比l1的大，插入到l1的前面;
                    ListNode* tmp = l2->next;
                    l2->next = l1;
                    l1 = l2;

                    l2 = tmp;

                    p1 = l1;
                    break;
                }

                l1 = l1->next;
            }
        }
        return p1;
    }
};