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

题意

将两个有序链表合并

思路

类比于两个有序线性表合并。并行遍历两个链表，并进行比较，若l1->val<l2->val，那么就连接l1的当前node，并且l1走到下一位。最后需要注意的是l1或l2没有遍历完时不需要再像有序顺序表一样一个一个遍历了，直接指向它就行。同时需要注意初始化，因为不能像有序表一样直接为空，这里需要根据大小关系指向l1或l2的头结点。最后需要注意的是需要用temp保存结果的头结点，因为到最后得到的result时结果的尾节点。

代码

/**
 * 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)
            return l2;
        if(!l2)
            return l1;
        ListNode* head1=l1;
        ListNode* head2=l2;
        ListNode* result=NULL;
        if(head1->val<head2->val)
        {
            result=head1;
            head1=head1->next;
        }
        else
        {
            result=head2;
            head2=head2->next;
        }
        ListNode *temp=result;
        while(head1&&head2)
        {
            if(head1->val<head2->val)
            {
                result->next=head1;
                result=result->next;
                head1=head1->next;
            }
            else
            {
                result->next=head2;
                result=result->next;
                head2=head2->next;
            }
        }
        if(head1)
            result->next=head1;
        if(head2)
            result->next=head2;
        // while(head1)
        // {
        //     result->next=head1;
        //     result=result->next;
        //     head1=head1->next;
        // }
        // while(head2)
        // {
        //     result->next=head2;
        //     result=result->next;
        //     head2=head2->next;
        // }
        return temp;
    }
};