Leetcode 21. Merge Two Sorted Lists

Merge two sorted ed 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

题目链接：https://leetcode.com/problems/merge-two-sorted-lists/

思路：用vector存放并排序，构建新的链表并返回，虽然方法很一般，但结果不错，这题只是考察链表的熟练程度吧

/**
 * Definition for singly- ed list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        vector<int> vec;
        while(l1!=NULL){
            vec.push_back(l1->val);
            l1=l1->next;
        }
        while(l2!=NULL){
            vec.push_back(l2->val);
            l2=l2->next;
        }
        sort(vec.begin(),vec.end());
        ListNode *head=NULL,*tail=NULL,*tmp=NULL;
        int len=vec.size();
        for(int i=0;i<len;i++)
        {
            if(tail==NULL)
            {
                tmp=(ListNode*)malloc(sizeof(ListNode));
                tmp->val=vec[i];
                tmp->next=NULL;
                tail=tmp;
                head=tail;
            }
            else
            {
                tmp=(ListNode*)malloc(sizeof(ListNode));
                tmp->val=vec[i];
                tmp->next=NULL;
                tail->next=tmp;
                tail=tmp;
            }
        }
        return head;
    }
};