合并两个排好序的链表

接下来要学习跟排序相关的算法了，在正式之前先来个小热身，将两个“已排好序”的链表进行merge操作，先编写一个代码框架，这个比较简单不过多解释：

#include <iostream>

struct node{
    int payload;
    node* next;
    node(int payload) {
        this->payload = payload;
        next = nullptr;
    }
};

class linkedlist
{
    node *head, *tail;
public:
    linkedlist() : head(nullptr), tail(nullptr) {

    }
    //从尾部插入元素
    void push_back(int value) {
        //TODO
    }

    //输出链表元素
    void output() {
        //TODO
    }
    
};

linkedlist merge(linkedlist a, linkedlist b) {
    //TODO
    return a;
}

int main(void) {

    linkedlist a, b;
    //按顺序插入数据
    a.push_back(4);  a.push_back(7);  a.push_back(20);
    b.push_back(2);  b.push_back(3);  b.push_back(9);  b.push_back(29);

    linkedlist result = merge(a, b);
      result.output();
    return 0;
}

接着来完善linkedlist类中的方法，对于一个链表通常会有：插入数据、取出数据、弹出数据、判断当前链表是否为空、输出整个链表，下面一一来完善：

#include <iostream>

struct node{
    int payload;
    node* next;
    node(int payload) {
        this->payload = payload;
        next = nullptr;
    }
};

class linkedlist
{
    node *head, *tail;
public:
    linkedlist() : head(nullptr), tail(nullptr) {

    }
    //从尾部插入元素
    void push_back(int value) {
        if(empty()) {
            //如果是空链表，则头尾节点都指向新插入的
            head = tail = new node(value);
        } else {
            tail->next = new node(value);
            tail = tail->next;
        }
    }

    //获得头一个元素的值
    int front() {
        if(empty()){
              throw "The list is empty.";
        }
        return head->payload;
    }

    //弹出头节点
    void pop_front() {
        if(empty()){
              throw "The list is empty.";
        }
        node* first_node = head;
        head = head->next;
        delete first_node;
    }

    bool empty() {
        return head == nullptr;
    }

    //输出链表元素
    void output() {
        node* iterator = head;
        while(iterator) {
            std::cout << iterator->payload << " ";
            iterator = iterator->next;
        }
        std::cout << std::endl;
    }
    
};

linkedlist merge(linkedlist a, linkedlist b) {
    //TODO
    return a;
}

int main(void) {

    linkedlist a, b;
    //按顺序插入数据
    a.push_back(4);  a.push_back(7);  a.push_back(20);
    b.push_back(2);  b.push_back(3);  b.push_back(9);  b.push_back(29);

    linkedlist result = merge(a, b);
      result.output();
    return 0;
}