题目难度：简单

题目描述：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围： 0≤n≤1000，−1000≤节点值≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

示例1:

输入：{1,3,5},{2,4,6} 返回值：{1,2,3,4,5,6}

思路1:链表归并

时间复杂度：O(n)，空间复杂度：0(1) 运行时间：4ms 占用内存：420KB

class Solution {
public:
  	ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
      	ListNode *pHead = new ListNode(0);
      	ListNode *cur = pHead, *cur1 = pHead1, *cur2 = pHead2;
      
      	while (cur1 && cur2) {
          	if (cur1->val <= cur2->val) {
              	cur->next = cur1;
              	cur1 = cur1->next;
            } else {
              	cur->next = cur2;
              	cur2 = cur2->next;
            }
          	cur = cur->next;
        }
      
      	while (cur1) {
          	cur->next = cur1;
          	cur1 = cur1->next;
          	cur = cur->next;
        }
      
      	while (cur2) {
          	cur->next = cur2;
          	cur2 = cur2->next;
          	cur = cur->next;
        }
      
      	return pHead->next;
    }
}

思路2:双指针递归

时间复杂度：O(n)，空间复杂度：0(n) 运行时间：4ms 占用内存：512KB

class Solution {
public:
  	ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
      
      	if(!pHead1) return pHead2;
      	if(!pHead2) return pHead1;
      
      	if(pHead1->val <= pHead2->val) {
          	pHead1->next = Merge(pHead1->next, pHead2);
          	return pHead1;
        } else {
          	pHead2->next = Merge(pHead1, pHead2->next);
          	return pHead2;
        }
    }
}

🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡🤡