首页 > 代码库 > Leetcode-21 Merge Two Sorted Lists

Leetcode-21 Merge Two Sorted Lists

#21.   Merge Two Sorted Lists

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.

题解:分情况考虑:当两个链表有一个为空的时候,返回另一个链表即可;

当两个链表都不为空时,依次进行比较l1和l2的值,直至某一链表指针为空,之后直接将另一链表的剩余部分插入链表尾部即可。

/**
 * 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) {
        ListNode* head=new ListNode(0);
        ListNode* ret=head;
        if(l1==NULL&&l2!=NULL)
            return l2;
        if(l1!=NULL&&l2==NULL)
            return l1;
        while(l1!=NULL&&l2!=NULL)
        {
            if(l1->val<=l2->val)
            {
                head->next=l1;
                l1=l1->next;
            }
            else
            {
                head->next=l2;
                l2=l2->next;
            }
            head=head->next;
        }
        while(l1)
        {
            head->next=l1;
            l1=l1->next;
            head=head->next;
        }
         while(l2)
        {
            head->next=l2;
            l2=l2->next;
            head=head->next;
        }
        return ret->next;
    }
};

 

Leetcode-21 Merge Two Sorted Lists