leetCode(8):merge two sorted list 分类： leetCode 2015-06-18 08:12 136人阅读 评论(0) 收藏

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.

/**
 * 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* head=NULL;
    head=((l1->val) < (l2->val))?  l1:l2;
    ListNode* p2=NULL;
    p2=((l1->val) >= (l2->val))?  l1:l2;
    
    ListNode* p1=head;
    
    while(p1->next && p2)
    {
    if((p1->next->val) <= (p2->val))
    p1=p1->next;
    else
    {
    ListNode* tmp1=p1->next;
    ListNode* tmp2=p2->next;
    p1->next=p2;
    p2->next=tmp1;
    p1=p2;
    p2=tmp2;
    }
    }
    
    if(!(p1->next))
    p1->next=p2;
    return head;
    }
};