数据结构-合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。

分析：考虑两个表是否为NULL。

/*
剑指offer面试题17
太懒没有写链表的创建函数，而是直接创建好。
将就看吧！
在windows下注释居然不能放在第一行！
*/
#include <iostream>

using namespace std;

struct ListNode{
    ListNode* Next;
    int data;
};

//神乎乎的递归，表示不会用！
ListNode* MergeList(ListNode* Fhead,ListNode* Shead){
    if(Fhead == NULL){
        return Shead;
    }
    if(Shead == NULL){
        return Fhead;
    }
    ListNode* p = NULL;

    if(Fhead->data < Shead->data){
        p = Fhead;
        p->Next = MergeList(Fhead->Next,Shead);
    }
    else{
        p = Shead;
        p->Next = MergeList(Fhead,Shead->Next);
    }

    return p;
}

int main()
{
    ListNode* Fhead = new ListNode;
    ListNode* FOne = new ListNode;
    ListNode* FTwo = new ListNode;
    ListNode* Ftail = new ListNode;

    Fhead->data = 0;
    Fhead->Next = FOne;
    FOne->data = 2;
    FOne->Next = FTwo;
    FTwo->data = 4;
    FTwo->Next = Ftail;
    Ftail->data = 6;
    Ftail->Next = NULL;

    ListNode* Shead = new ListNode;
    ListNode* SOne = new ListNode;
    ListNode* STwo = new ListNode;
    ListNode* Stail = new ListNode;

    Shead->data = 1;
    Shead->Next = SOne;
    SOne->data = 3;
    SOne->Next = STwo;
    STwo->data = 4;
    STwo->Next = Stail;
    Stail->data = 7;
    Stail->Next = NULL;

    ListNode* result = MergeList(Fhead,Shead);

    while(result->Next != NULL){
        cout << result->data << " ";
        result = result->Next;
    }

    return 0;
}