题目:

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

第一种解题方法

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1 || !l2)
            return l1 ? l1 : l2;

        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

Status	Runtime	Language
Accepted	8ms	cpp

Time complexity

• T(n) = 1 + T(n-1)
• T(n) = O(n)

时间复杂度为O(n)

---

第二种解题方法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode tmp(0);
	ListNode* tail=&tmp;
	while(l1 && l2){
	    if(l1->val < l2->val){
	        tail->next=l1;
	        l1=l1->next;
	    }else{
	        tail->next=l2;
            l2=l2->next;
	    }
	    tail=tail->next;
	}
	if(l1)
	    tail->next=l1;
	if(l2)
	    tail->next=l2;
	
	return tmp.next;
    }
};

Status	Runtime	Language
Accepted	13ms	cpp

Time complexity

• T(n) = n + T(n-1)
• T(n) = O(n²)

时间复杂度为O(n²)