题解 | #合并两个排序的链表#
合并两个排序的链表
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if(!pHead1){//特判
return pHead2;
}
//一个链表插入到另一个链表中
ListNode* res = new ListNode(INT_MIN);
res->next = pHead1;
ListNode* pre = res;
ListNode* cur = pre->next; //用于pHead1
while(pHead2){
int hasInsert = 0;
int isTail = 0;
while(!hasInsert){
if(cur->val > pHead2->val){
ListNode* tmp = pHead2->next;
pHead2->next = cur;
pre->next = pHead2;
pre = pre->next;
pHead2 = tmp;
hasInsert = 1;
break;
}else if(cur->next){
pre = pre->next;
cur = pre->next;
}else{
isTail = 1;
break;
}
}
if(isTail == 1){
cur->next = pHead2;
break;
}
}
return res->next;
}
};
主要思路为将一个链表插入到另一个链表中，因为都是递增的链表，所以pHead2（不一定是开头那个，为了省空间没有新建）一定大于cur, 所以只要递增cur找到比pHead2大的cur, 插到前面就好，如果没找到，说明到尾部了，之间把后面的都接上去。
投递完美世界等公司10个岗位
