16.合并两个排序的链表.md

16.合并两个排序的链表

题目描述

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

解题思路

• 迭代思想，两个指针*next1，*next2分别指向两个链表的下一个结点，一个指针*p指向已经合并的链表的最后一个结点，比较next1和next2的val，把小的那个接在p的后面，然后next1或者next2指针向后移动（取决于哪个接在p的后面了）。

• 递归思想，看代码就懂了，比较小的结点往后走，继续合并。

代码

• 方法一，迭代

/*
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;
        else if(pHead2 == NULL) return pHead1;
        
        ListNode *pHead3, *next1, *next2, *p;
        if(pHead1->val <= pHead2->val) {
            pHead3 = pHead1;
            next1 = pHead1->next;
            next2 = pHead2;
        }
        else {
            pHead3 = pHead2;
            next1 = pHead1;
            next2 = pHead2->next;
        }
        p = pHead3;
        while(next1 && next2){
            if(next1->val <= next2->val){
                p->next = next1;
                p = next1;
                next1 = next1->next;
            }
            else{
                p -> next = next2;
                p = next2;
                next2 = next2->next;
            }
        }
        if(next1 == NULL) p->next = next2;
        else p->next = next1;
        return pHead3;
    }
};

• 方法二，递归

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
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;
       }       
   }