本文主要是介绍剑指offer——JZ25 合并两个排序的链表 解题思路与具体代码【C++】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述与要求
合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com)
题目描述
输入两个递增的链表，单个链表的长度为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}
二、解题思路
首先我们需要对两个表进行判断。一旦有一个表为空，则直接返回另一个表的头结点即可，如果两个链表都为空，则返回NULL。
然后就是两个表都不为空的情况下如何去合并两个表，我们可以定义三个辅助指针pa、pb、pc，分别用于遍历需要合并的两个链表还有合并成的第三个链表，还有定义一个头结点pHead3，同于最后返回结果。接着分别判断两个表的第一个结点，取小的一方作为合并后的头结点，也就是pHead3所要指向的结点。
然后就是对两个表同时进行遍历，然后判断当前pa和pb所指向的结点的值的大小，小者使pc指向它（合并），然后指针后移遍历下一个结点，一直到有一个表为空或者两个表都为空的情况则结束。
当有一个表为空时，则只需要将剩下的那个表的结点以尾插法插入C中即可，可以用while，也可以利用条件表达式（更为简便）
三、具体代码
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {// write code hereif(pHead1==NULL&&pHead2!=NULL){ //如果表1为空 表2不为空则直接返回表2return pHead2;}else if(pHead1!=NULL&&pHead2==NULL){ //如果表2为空 表1不为空则直接返回表1return pHead1;}else if(pHead1==NULL&&pHead2==NULL){ //两个表都为空返回NULreturn NULL;}else{ListNode *pa,*pb,*pc,*q,*pHead3;pa=pHead1;pb=pHead2;if(pa->val<=pb->val){pc=pa;pHead3=pc;pa=pa->next;}else{pc=pb;pHead3=pc;pb=pb->next;}while(pa&&pb){ //两表都不为空if(pa->val<=pb->val){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}// while(pa){ //表1不为空// q=pa->next;// pa->next=NULL;// pc->next=pa;// pc=pa;// pa=q;// }// while(pb){// q=pb->next;// pb->next=NULL;// pc->next=pb;// pc=pb;// pb=q;// }pc->next=pa?pa:pb;return pHead3;}}
};这篇关于剑指offer——JZ25 合并两个排序的链表 解题思路与具体代码【C++】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
