day7-1110-leetcode之排序2-Merge Two Sorted Lists

LeetCode-Merge Two Sorted Lists

• • 题目
  • 等级
  • 分析
  • C++实现
  • 结果

题目

Merge two sorted linked lists and return it as a new list. e new list should be made by splicing together the nodes of the first two lists.

等级

easy

分析

无

C++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//LeetCode, Merge Two Sorted Lists
// 时间复杂度 O(m+n)，空间复杂度 O(1)
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(-1);
		for( ListNode* p= &head; l1!= nullptr || l2 != nullptr; p=p->next){
			int val1= l1 == nullptr ? INT_MAX : l1->val;
			int val2= l2 == nullptr ? INT_MAX : l2->val; 
			if(val1 <= val2){
				p->next = l1;
				l1 = l1->next;
			}else{
				p->next = l2;
				l2 = l2->next;
			}
		}	
		return head.next;
    }
};

           

结果

Success

Details:

Runtime: 8 ms, faster than 88.15% of C++ online submissions for Merge Two Sorted Lists.