牛客热题：合并升序链表

本文主要是介绍牛客热题：合并升序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

在这里插入图片描述

文章目录

牛客热题：合并升序链表
- 题目链接
- 方法一：简单迭代
- - 思路
  - 代码
  - 复杂度
- 方法二：递归
- - 思路
  - 代码
  - 复杂度

牛客热题：合并升序链表

题目链接

合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com)

方法一：简单迭代

思路

简单迭代：

设置一个哨兵位头节点head
同时遍历两个有序链表，谁的值小就将其的值尾插到哨兵头节点所在的指针；
最后可能会有某一个有序链表未被遍历完毕的情况：那么我们分别遍历即可

代码

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {//申请一个哨兵位ListNode* head = new ListNode(0);ListNode* cur = head;while(pHead1 != nullptr && pHead2 != nullptr){if(pHead1->val <= pHead2->val){cur->next = pHead1;cur = cur->next;pHead1 = pHead1->next;}else {cur->next = pHead2;cur = cur->next;pHead2 = pHead2->next;}}//p1未完的情况while(pHead1 != nullptr){cur->next = pHead1;cur = cur->next;pHead1 = pHead1->next;}//p2未完的情况while(pHead2 != nullptr){cur->next = pHead2;cur = cur->next;pHead2 = pHead2->next;}return head->next;}

复杂度

时间复杂度：O(N + M) ,遍历一次两个链表

空间复杂度：O(1) ,只使用了常数量级的变量个数

方法二：递归

思路

递归：

由题意可知Merge(ListNode* pHead1, ListNode* pHead2)的功能是合并这两个链表并使新链表中的节点仍然是递增排序的。
那么我们可以利用这个特性，得到两个结论：

①当pHead1->val <= pHead2->val

这时候我们当前的节点一定是以pHead1开头，并且pHead1->next的后面紧接着是pHead1->next和pHead2有序排列好的链表，那么可以表示为如下的代码：
```
        if(pHead1->val <= pHead2->val){pHead1->next = Merge(pHead1->next, pHead2);return pHead1;}
```
②当pHead1->val > pHead2->val

则可以表示为：
```
        else {pHead2->next = Merge(pHead1, pHead2->next);return pHead2;}
```
截止条件：当pHead1或者pHead2中有一个是空指针的时候，我们就返回其中哪个不为空的指针；

若两个都为空指针，那么就随便返回其中一个

代码

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr || pHead2 == nullptr)return pHead1 == nullptr ? pHead2 : pHead1;if(pHead1->val <= pHead2->val){pHead1->next = Merge(pHead1->next, pHead2);return pHead1;}else {pHead2->next = Merge(pHead1, pHead2->next);return pHead2;}}