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==NULL) return l2; if(l2==NULL) return l1; ListNode *p1=l1; ListNode *p2=l2; ListNode *head=NULL,*r=NULL; while(p1&&p2) { if(head==NULL) { if(p1->val<p2->val) { head=r=p1; p1=p1->next; } else { head=r=p2; p2=p2->next; } } else { if(p1->val<p2->val) { r->next=p1; p1=p1->next; } else { r->next=p2; p2=p2->next; } r=r->next; } } if(p1) r->next=p1; if(p2) r->next=p2; return head; } };