合并两个排序的链表

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

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

二、我的思路

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) returnpHead2; if(pHead2 == NULL) returnpHead1; 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; returnhead; } };