Merge Two Sorted Lists

描述

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.

分析

无

代码

  1. // Merge Two Sorted Lists
  2. // 时间复杂度O(min(m,n))，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
  6.         if (l1 == nullptr) return l2;
  7.         if (l2 == nullptr) return l1;
  8.         ListNode dummy(-1);
  9.         ListNode *p = &dummy;
  10.         for (; l1 != nullptr && l2 != nullptr; p = p->next) {
  11.             if (l1->val > l2->val) { p->next = l2; l2 = l2->next; }
  12.             else { p->next = l1; l1 = l1->next; }
  13.         }
  14.         p->next = l1 != nullptr ? l1 : l2;
  15.         return dummy.next;
  16.     }
  17. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/sorting/merge-sort/merge-two-sorted-lists.html