プログラミングアルゴリズム-受注リストのマージ

連結順序チェーンテーブル
本住所:http://blog.csdn.net/caroline_wendy/article/details/29352997
タイトル:
連結順序チェーンテーブルは、2つの昇順チェーンテーブルが与えられ、1つの連結後の昇順チェーンテーブルを返す.
ノード構造:
struct Node{
    int val;
    Node *next;
};
実装が必要な関数:
Node* mergeList(Node *list_a, Node* list_b)
コード:

/*
 * test.cpp
 *
 *  Created on: 2014.04.24
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>
#include <vector>

using namespace std;

struct Node{
	int val;
	Node *next;
};

Node* mergeList(Node *list_a, Node* list_b) {
	if (list_a == NULL) //       
		return list_b;
	else if (list_b == NULL)
		return list_a;

	Node* pMergedHead = NULL; //      

	if (list_a->val < list_b->val) {
		pMergedHead = list_a; //     
		pMergedHead->next = mergeList(list_a->next, list_b); //  
	} else {
		pMergedHead = list_b;
		pMergedHead->next = mergeList(list_a, list_b->next);
	}

	return pMergedHead;
}

Node* initList(const std::vector<int>& vi) {
	Node* pHead = new Node;
	Node* pTemp = pHead;

	for (std::size_t i=0; i<vi.size(); ++i) {
		pTemp->val = vi[i];

		if (i != vi.size()-1) { //    
			Node* pNode = new Node;
			pTemp->next = pNode;
			pTemp = pTemp->next;
		}
	}

	pTemp->next = NULL;

	return pHead;
}

void printList(Node* L) {
	Node* pTemp = L;
	while (pTemp->next != NULL) {
		std::cout << pTemp->val << " ";
		pTemp = pTemp->next;
	}
	std::cout << pTemp->val << " "; //       
	std::cout << std::endl;
}

int main(void) {
	std::vector<int> via = {1, 2, 3, 4, 5, 13};
	std::vector<int> vib = {2, 4, 5, 7, 9, 11};

	Node* list_a = initList(via);
	Node* list_b = initList(vib);
	std::cout << "list_a = "; printList(list_a);
	std::cout << "list_b = "; printList(list_b);

	Node* list_merge = mergeList(list_a, list_b);
	std::cout << "list_merge = "; printList(list_merge);

	return 0;
}

出力:

list_a = 1 2 3 4 5 13 
list_b = 2 4 5 7 9 11 
list_merge = 1 2 2 3 4 4 5 5 7 9 11 13