非递归

时间复杂度O(m+n)
空间复杂度O(1)
思路: 如有有一个链表为空，就返回另一个链表。创建一个虚拟头结点连接新的链表，当两个链表都不为空时，循环比较两个链表的头部元素大小，令新链表的下一个结点为值较小的结点，然后相应链表结点后移一位，每次循环完新链表的当前结点也后移一位，循环结束后，令新链表的下一个结点指向剩下的非空链表，返回新链表头部，也就是虚拟头结点的后一个结点。

  1. class Solution {
  2. public:
  3.     ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
  4.         // 如果有一个链表为空就返回另外一个链表
  5.         if (pHead1 == nullptr) return pHead2;
  6.         if (pHead2 == nullptr) return pHead1;
  7.         // 创建一个虚拟头结点连接新链表的头部
  8.         ListNode *dummyNode = new ListNode(0);
  9.         ListNode *cur = dummyNode;
  10.         // 当两个链表都不为空时
  11.         while (pHead1 && pHead2) {
  12.             // 循环比较两个链表的头部结点元素大小
  13.             if (pHead1->val <= pHead2->val) {
  14.                 // 令新链表的下一个结点指向值较小的结点
  15.                 cur->next = pHead1;
  16.                 // 然后相应链表结点后移一位
  17.                 pHead1 = pHead1->next;
  18.             } else {
  19.                 cur->next = pHead2;
  20.                 pHead2 = pHead2->next;
  21.             }
  22.             // 每次循环完新链表的当前结点也后移一位
  23.             cur = cur->next;
  24.         }
  25.         // 循环结束后，令新链表的下一个结点指向剩下的非空链表
  26.         cur->next = pHead1 ? pHead1 : pHead2;
  27.         ListNode *res = dummyNode->next;
  28.         delete dummyNode;
  29.         // 返回新链表头部，也就是虚拟头结点的后一个结点
  30.         return res;
  31.     }
  32. };

递归

递归调用m+n次
时间复杂度O(m+n)：O(1) * (m+n)
// 递归调用的次数和每次的时间复杂度的乘机
空间复杂度O(m+n)

  1. class Solution {
  2. public:
  3.     ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
  4.         // 如果有一个链表为空就返回另外一个链表
  5.         if (!pHead1) return pHead2;
  6.         if (!pHead2) return pHead1;
  7.         // 比较两个链表头部结点的值，如果p1头部元素值小
  8.         // 那么最后返回的就应该是p1头部
  9.         // 同时将p1的下一个结点指定为递归合并p1后面结点和p2结点后的头部结点
  10.         if (pHead1->val <= pHead2->val) {
  11.             pHead1->next = Merge(pHead1->next, pHead2);
  12.             return pHead1;
  13.         // 相反如果p2值大于p1
  14.         // 最后返回的就应是p2的头部结点
  15.         // p2的下一个结点为p2后面结点和p1所有结点合并后的头部结点
  16.         } else {
  17.             pHead2->next = Merge(pHead2->next, pHead1);
  18.             return pHead2;
  19.         }
  20.     }
  21. };