合并两个排序的链表

合并两个排序的链表 一、题目要求

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

二、我的思路

1、比较两个链表的头结点大小，哪个小就将其作为新链表的头结点；
2、依次比较两个链表节点的大小，将一个链表合并到另一个链表中；
3、合并完之后，剩余部分合并到新链表最后；

我的代码 /* 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 == NULL) return pHead2; if(pHead2 == NULL) return pHead1; ListNode *head = NULL; if(pHead1->val <= pHead2->val){ head = pHead1; pHead1 = pHead1->next; } else{ head = pHead2; pHead2 = pHead2->next; } ListNode *p = head; while(pHead1 && pHead2){ if(pHead1->val <= pHead2->val){ p->next = pHead1; pHead1 = pHead1->next; } else{ p->next = pHead2; pHead2 = pHead2->next; } p = p->next; } if(pHead1) p->next = pHead1; else if(pHead2) p->next = pHead2; return head; } };