编程算法之合并有序链表

编程算法之合并有序链表2015-09-06题目:

合并有序链表, 给定两个升序的链表, 返回一个合并之后的升序链表.

节点结构:

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

作者：csdn博客 Caroline-Wendy