# 14 line clean C++ Solution

• ``````class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode dummy(INT_MIN);
ListNode *tail = &dummy;

while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}

tail->next = l1 ? l1 : l2;
return dummy.next;
}
};``````

• Question, if l1 is more than 1 nodes longer than l2. This may not work. Am I right?

• Probably not. This code works regardless of l1 and l2's lengths. Can u give a concrete counter-example where it fails?

• Sorry, I think your right. :)

• This post is deleted!

• ``````ListNode *mergeTwoLists(ListNode *l1, ListNode *l2){
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
ListNode *small = l1->val < l2->val ? l1 : l2;
ListNode *large = l1->val >= l2->val ? l1 : l2;
while (small->next){
if (small->next->val < large->val)
small = small->next;
else{
ListNode *temp = small->next;
small->next = large;
small = large;
large = temp;
}
}
small->next = large;
return l1->val < l2->val ? l1 : l2;
}``````

• beautiful code, but what is the function of dummy(),thank you!

• Dummy is there to store a pointer to the new head of the list. Tail starts off as what will be the head, but it changes, so dummy stores the pointer to the head.

• JAVA version

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null || l2 == null ) {
return l1 == null ? l2 : l1;
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while(l1 != null && l2 != null ) {
if(l1.val < l2.val ) {
current.next = l1;
l1 = l1.next;
}
else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 == null ? l2 : l1;
return dummy.next;
}
}
``````

• I think everyone forgot about the condition :
Merge two sorted linked lists and return it as "A NEW LIST".

However, the checker did not check for that in this program.

• what did the dumpy function do ? thanks.

• @Yuan-Yen This works.
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* l3 = new ListNode(0);
ListNode *l4;
l4=l3;
if(!l1)
return l2;
if(!l2)
return l1;

``````    while(l1 && l2)
{
if(l1->val < l2->val)
{
l3->next =  new ListNode(l1->val);
l1 = l1->next;
}
else
{
l3->next = new ListNode(l2->val);
l2 = l2->next;
}
l3=l3->next;
}

while(l1)
{
l3->next = new ListNode(l1->val);
l1 = l1->next;
l3=l3->next;

}

while(l2)
{
l3->next = new ListNode(l2->val);
l2 = l2->next;
l3=l3->next;

}

return l4->next;
}``````

• @xiaohui7 beautiful use of dummy node in the beginning! It takes me many lines of code to take care of the initialization.

• It can be simpler:

``````    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode *tail = &dummy;
while(l1 && l2) {
ListNode *& node = l1->val < l2->val ? l1 : l2;
tail = tail->next = node;
node = node->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
``````

P.S. I didn't know I can reference a value of the "?:" expression :P But when I try it worked!

• The use of dummy helps in simplifying initialization code greatly. If its not forced upon that new lists should only reuse nodes from existing lists, the solution is good.

• I get the approach where `dummy` is initialized but the actual list we return starts from the next node. However; I don't see how `dummy.next` isn't `NULL`? Does modifying `tail->next` in the first iteration also change `dummy.next`? (I still struggle with pointers...)

• Beautiful solution ! Especially at the end..

• Actually you need free the first node memory before the function return. just like this:

``````tail = dummy;
dummy = dummy->next;
delete tail
return dummy
``````

• 8-line version of it :)

``````struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode * l3_tail = &(l3_head);
while(l1 != NULL && l2 != NULL ){
l3_tail = l3_tail->next = (l1->val <= l2->val)? l1 : l2;
void * dummy = (l1->val <= l2->val)? (l1 = l1->next) : (l2 = l2->next);
}
l3_tail->next = (l1 != NULL)? l1 : l2;