剑指offer 面试题17: 合并两个排序的链表
提交网址: http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
分析:
此题是leetcode 148. Sort List https://leetcode.com/problems/sort-list/ 的简化版
AC代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode *res, *p;
if(pHead1==NULL) return pHead2;
if(pHead2==NULL) return pHead1;
if(pHead1->val < pHead2->val)
{
res=pHead1;
pHead1=pHead1->next;
}
else {
res=pHead2;
pHead2=pHead2->next;
}
p=res;
while(pHead1 != NULL && pHead2 != NULL)
{
if(pHead1->val < pHead2->val)
{
p->next=pHead1;
pHead1=pHead1->next;
}
else {
p->next=pHead2;
pHead2=pHead2->next;
}
p=p->next;
}
if(pHead1 != NULL) p->next=pHead1;
else if(pHead2 != NULL) p->next=pHead2;
return res;
}
};