首页 > 代码库 > [LintCode] Merge Two Sorted Lists 混合插入有序链表
[LintCode] Merge Two Sorted Lists 混合插入有序链表
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.
Have you met this question in a real interview?
Yes
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; }};
[LintCode] Merge Two Sorted Lists 混合插入有序链表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。