【牛客刷题专栏】0x26:JZ25 合并两个排序的链表(C语言编程题)

前言

• 个人推荐在牛客网刷题(点击可以跳转)，它登陆后会保存刷题记录进度，重新登录时写过的题目代码不会丢失。
• 个人刷题练习系列专栏：个人CSDN牛客刷题专栏。 题目来自：牛客/题库 / 在线编程 / 剑指offer：
  

---

问题描述：

• 输入两个递增的链表，单个链表的长度为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,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
  

---

举例：

//示例1：
//输入：
{1,3,5},{2,4,6}
//返回值：
{1,2,3,4,5,6}
//==========================
//示例2：
//输入：
{},{}
//返回值：
{}
//==========================
//示例3：
//输入：
{-1,2,4},{1,3,4}
//返回值：
{-1,1,2,3,4,4}

---

解法思路：

• 采用递归法对两个链表的节点进行比较，将小的头节点取出，并将其添加到新的链表后面，剩下的部分再进行比较，重复上述过程，直到两个链表为空。

---

代码结果：

```/*** struct ListNode {*	int val;*	struct ListNode *next;* };** C语言声明定义全局变量请加上static，防止重复定义*//*** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {// write code hereif(pHead1 == NULL)return pHead2;if(pHead2 == NULL)return pHead1;struct ListNode *phead = NULL;if(pHead1->val < pHead2->val){phead = pHead1;phead->next = Merge(pHead1->next, pHead2);}else{phead = pHead2;phead->next = Merge(pHead1, pHead2->next);}return phead;
}

---

---

结束语

• 以上就是该C语言编程题的内容。可以在牛客尝试刷几道题目来练习实践。牛客网刷题(点击可以跳转)，可以尝试注册使用。
• 题目来自：牛客/题库 / 在线编程 / 剑指offer：