返回

[Leetcode]21. Merge Two Sorted Lists(C++)

题目描述

题目链接:21. Merge Two Sorted Lists

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

例子

例子 1

Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]

例子 2

Input: l1 = [], l2 = [] Output: []

例子 3

Input: l1 = [], l2 = [0] Output: [0]

Constraints

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both l1 and l2 are sorted in non-decreasing order.

解题思路

由于两个链表都已经排好序,所以只需要用两个指针指向两个链表,每次比较两个节点,并将当前节点指向较小的那一个(如果其中一个为空则指向另一个)即可。

代码如下:

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

        return dummy->next;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 21.MergeTwoSortedLists.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy