首页 > 代码库 > [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->null2->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 混合插入有序链表