Merge Two Sorted Lists

LeetCode笔记 阅读(67)

编号 : 21      
难度 : <font color="green">Easy</font>

# 题目 :  
>Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
>
>**Example**:
>
>>**Input**: 1->2->4, 1->3->4  
>>**Output**: 1->1->2->3->4->4  
>

# 解 :  
```Cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
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的第一个节点是最小的 */
            swap(l1, l2);
        }
        auto ret = l1;

        /* 把链表2往链表1里插 */
        while(l2 != nullptr)
        {
            
            if(l1->next == nullptr)
            {
                l1->next = l2;
                break;
            }
            else if(l1->next->val > l2->val)
            {
                auto temp = l2;
                l2 = l2->next;

                temp->next = l1->next;
                l1->next = temp;
            }
            else
            {
                l1 = l1->next;
            }
        }
        
        return ret;
    }
};
```

# 分析 :  
这道题要求将两个升序的链表合并为一个升序的链表。

把其中一个往另一个里面插入即可,上述代码中将第一个元素较小的链表(`L1`)作为**被插入**的链表,如果`L1`描到尾部,就把`L2`剩余的元素接到`L1`的尾部上去。另外需要判断一下输入为`nullptr`的情况。

Markdown使用 帮助