题目:
输入两个单调递增的链表, 输出两个链表合成后的链表, 当然我们需要合成后的链表满足单调不减规则.
分析:
可以用一个新的节点, 来去比较两个单调递增的链表当前节点的值, 如果 p1 当前的值小于 p2, 则新的节点的 next=p1,p1 移到下一个节点, 新的节点 p 也要移动到下一个节点.
当然也可以用递归来做. C++ 常规做法, Java 递归实现.
程序:
- C++
- class Solution {
- public:
- ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
- {
- if(pHead1 == nullptr)
- return pHead2;
- if(pHead2 == nullptr)
- return pHead1;
- ListNode resHead(0);
- ListNode* p = &resHead;
- 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;
- if(pHead2)
- p->next = pHead2;
- return resHead.next;
- }
- };
- Java
- public class Solution {
- public ListNode Merge(ListNode list1,ListNode list2) {
- if(list1 == null) return list2;
- if(list2 == null) return list1;
- if(list1.val < list2.val){
- list1.next = Merge(list1.next, list2);
- return list1;
- }
- else{
- list2.next = Merge(list1, list2.next);
- return list2;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3294287.html