Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.
Example
Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null.
LeetCode上的原题，请参见我之前的博客Merge Two Sorted Lists。
解法一：
class Solution { public: /** * @param ListNode l1 is the head of the linked list * @param ListNode l2 is the head of the linked list * @return: ListNode head of linked list */ ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *dummy = new ListNode(-1), *cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = 1l; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return dummy->next; } };
解法二：
class Solution { public: /** * @param ListNode l1 is the head of the linked list * @param ListNode l2 is the head of the linked list * @return: ListNode head of linked list */ ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } };
解法三：
class Solution { public: /** * @param ListNode l1 is the head of the linked list * @param ListNode l2 is the head of the linked list * @return: ListNode head of linked list */ ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if (!l1) return l2; if (!l2) return l1; ListNode *head = (l1->val < l2->val) ? l1 : l2; ListNode *nonHead = (l1->val < l2->val) ? l2 : l1; head->next = mergeTwoLists(head->next, nonHead); return head; } };
解法四：
class Solution { public: /** * @param ListNode l1 is the head of the linked list * @param ListNode l2 is the head of the linked list * @return: ListNode head of linked list */ ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if (!l1 || (l2 && l1->val > l2->val)) swap(l1, l2); if (l1) l1->next = mergeTwoLists(l1->next, l2); return l1; } };
本文转自博客园Grandyang的博客，原文链接：混合插入有序链表Merge Two Sorted Lists ，如需转载请自行联系原博主。
