编程算法之合并有序链表

题目:

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

节点结构:

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

返回栏目页：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

作者：csdn博客 Caroline-Wendy

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索递归
， return
， node
， next
， 链表 算法
， 链表 递归
， 链表合并
， 有序链表
升序
合并两个有序链表、两个有序单链表的合并、合并有序链表、java合并两个有序链表、有序链表的合并，以便于您获取更多的相关知识。