首页 > 代码库 > Merge Two Sorted Lists

Merge Two Sorted Lists

class Solution { public:     int listSize(ListNode* l){         if(l==NULL) return 0;         int len=1;         ListNode* p=l;         while (p->next)         {             p=p->next;             ++len;         }         return len;     }     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {         if(l1==NULL)              return l2;         if(l2==NULL)              return l1;         int len1=listSize(l1);int len2=listSize(l2);         ListNode* p=l1;         ListNode* result=(ListNode*)malloc(sizeof(ListNode));         result->next=NULL;         result->val=p->val;         ListNode* q1=result;         for (int i=1;i<len1;++i)         {             p=p->next;             ListNode* s=(ListNode*)malloc(sizeof(ListNode));             s->val=p->val;             s->next=q1->next;             q1->next=s;             q1=q1->next;         }         ListNode* q=l2;         for (int i=0;i<len2;++i)         {             int time=0;             ListNode* curNode=result;             ListNode* preNode=result;             int temp=q->val;             while(curNode!=NULL&&curNode->val<temp){                 if(time!=0){                     preNode=preNode->next;                 }                 curNode=curNode->next;                 ++time;             }             if(time==0){                 ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));                 newNode->val=temp;                 newNode->next=result;                 result=newNode;                 q=q->next;             }else{                 ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));                 newNode->val=temp;                 newNode->next=preNode->next;                 preNode->next=newNode;                 q=q->next;             }         }         return result;              } };

 

Merge Two Sorted Lists