Description:

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.

Code:

1  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 2         if (!l1) 3             return l2; 4         else if (!l2) 5             return l1; 6         else 7         { 8             ListNode * head, *p, *q, *result; 9             if (l1->val < l2->val)10             {11                 head = l1;12                 p = l1->next;13                 q = l2;14             }15             else16             {17                 head = l2;18                 p = l1;19                 q = l2->next;20             }21             result = head;22             while (p&&q)23             {24                 if (p->val < q->val)25                 {26                     result->next = p;27                     result = p;28                     p = p->next;29                 }30                 else31                 {32                     result->next = q;33                     result = q;34                     q = q->next;35                 }36             }37             result->next = (p==NULL)?q:p;38              return head; 39         }40     }