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;
}
};
14 line clean C++ Solution


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; }

JAVA version
/** * Definition for singlylinked list. * 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; } }

@YuanYen 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!

8line version of it :)
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode l3_head; 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; return l3_head.next; }

@xiaohui7 I think this solution is not quite right... We are supposed to focus on "a new list". Otherwise,if we need to delete the new list, the old one will be affected too...