Solution:pointer manipulation.
/** * 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) { // Start typing your C/C++ solution below // DO NOT write int main() function if(l1==NULL) return l2; if(l2==NULL) return l1; ListNode* c1 = (l1->val<=l2->val?l1:l2); //pointing to the head with the smaller val ListNode* c2 = (l1->val<=l2->val?l2:l1); //pointing to the head with the larger val while(c1->next!=NULL && c2!=NULL){ if(c1->val<=c2->val && c2->val<=c1->next->val){ //insert c2 behind of c1 ListNode* tmp = c2->next; c2->next = c1->next; c1->next = c2; //advance both pointers c1 = c1->next; c2 = tmp; } else c1 = c1->next; } if(c1->next==NULL) c1->next = c2; return (l1->val<=l2->val?l1:l2); } };
No comments:
Post a Comment