[LeetCode] Merge Two Sorted Lists

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.

思路：

和merge sort中的merge过程很像。两个list l1, l2的head始终指向它们各自的最小节点，取其中更小的那个插入新的list l3中即可。直到l1, l2中任意一个节点用完，则将另一个list剩余节点插入l3最后即可。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *l3 = new ListNode(-1); ListNode *t3 = l3; while(l1 && l2) { if(l1->val<=l2->val) { t3->next = l1; l1 = l1->next; } else { t3->next = l2; l2 = l2->next; } t3 = t3->next; t3->next = NULL; } t3->next = l1 ? l1 : l2; ListNode* temp = l3; l3 = l3->next; delete temp; return l3; } };