合并两个排序的链表

题目描述

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

/*
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) return pHead2;
        if(!pHead2) return pHead1;
        
        struct ListNode* F = pHead1, *L = pHead2, *f, *l; 
        
        while(F && L){
            if(F->val <= L->val){//F表比L表小
                while(F){//找到F中比L大的边界，取前一个小的
                    if(F->val > L->val )
                        break;
                    f = F;
                    F = F->next;
                }
                f->next = L;//连接
            }else {//F表比L表大
                while(L){//找到L中比F大的边界，取前一个小的
                    if(L->val > F->val )
                        break;
                    l = L;
                    L = L->next;
                }
                l->next = F;//连接
            }
        }
        if(pHead1->val <= pHead2->val) 
            return pHead1;
        else return pHead2;   
    }
};

递归版：

/*
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) return pHead2;
        if(!pHead2) return pHead1;
        
        if(pHead1->val <= pHead2->val){
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        }
       
        pHead2->next = Merge(pHead2->next, pHead1);
        return pHead2;
        
    }
};

STL:

merge：将两个有序的序列合并为一个有序的序列。
原型：

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,OutputIterator result );
template <class InputIterator1, class InputIterator2,class OutputIterator, class Compare>
OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp );

实例：

#include <iostream> 
#include <list> 
#include <iomanip> 
using namespace std; 
//网上的例子
int main() 
{ 
    // 有序数据  
  int A1[]={1,2,3,4,5,6}; 
    int A2[]={2,4,6,8,9,10}; 
    //有序链表  
  list<int> iL1(A1, A1+6); 
    list<int> iL2(A2, A2+6); 
    iL1.merge(iL2); //就这么用，两个有序链表，合并
    list<int>::iterator it = iL1.begin(); 
    while(it!=iL1.end()) 
    { 
        cout<<setw(3)<<*it++; 
    } 
    cout<<endl; 
    system("pause"); 
    return 0; 
}
输出为：
  1  2  2  3  4  4  5  6  6  8  9 10

// merge algorithm example//网上的例子
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  vector<int> v(10);
  vector<int>::iterator it;

  sort (first,first+5);
  sort (second,second+5);
  merge (first,first+5,second,second+5,v.begin());

  cout << "The resulting vector contains:";
  for (it=v.begin(); it!=v.end(); ++it)
    cout << " " << *it;

  cout << endl;
  
  return 0;
}