【编程题目】请修改 append 函数，利用这个函数实现两个非降序链表的并集

浏览数：22 / 时间：2015年06月11日

42.请修改 append 函数，利用这个函数实现（链表）：
两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果，不能修改两个链表的数据。

感觉网上理解题意略有不同，我理解的题意：

只是输出最后的结果，不用生成一个新的链表，也不修改原有链表。

给的数据非降序就是 1 1 2 2 3 这样可以有重复数字的递增

输出时，不显示重复的数字。

基于这些理解，题目不难，代码如下：

/*
42.请修改 append 函数，利用这个函数实现（链表）：
两个非降序链表的并集，1->2->3  和  2->3->5  并为  1->2->3->5
另外只能输出结果，不能修改两个链表的数据。
start time = 19:29
end time = 19:57
*/

#include <iostream>
using namespace std;

typedef struct List
{
    int m_value;
    List * p_next;
}List;

void append(List * L1, List * L2)
{
    List * p1 = L1;
    List * p2 = L2;
    //两个链表都没走空
    while(p1 != NULL && p2 != NULL)
    {
        int v;
        if(p1->m_value > p2->m_value)
        {
            v = p2->m_value;
            cout << p2->m_value;
            while(p2 != NULL && p2->m_value == v)
                p2 = p2->p_next;
        }
        else if(p1->m_value < p2->m_value)
        {
            v = p1->m_value;
            cout << p1->m_value;
            while(p1 != NULL && p1->m_value == v)
                p1 = p1->p_next;
        }
        else
        {
            v = p1->m_value;
            cout << p1->m_value<<" ";
            while(p1 != NULL && p1->m_value == v)
                p1 = p1->p_next;
            while(p2 != NULL && p2->m_value == v)
                p2 = p2->p_next;
        }

        if(p1 == NULL && p2 == NULL)
            cout<<endl;
        else
            cout<<"->";
    }
    //若p1未走空
    while(p1 != NULL)
    {
        int v = p1->m_value;
        cout << p1->m_value;
        while(p1 != NULL && p1->m_value == v)
            p1 = p1->p_next;
        if(p1 == NULL)
            cout<<endl;
        else
            cout<<"->";
    }
    //若p2未走空
    while(p2 != NULL)
    {
        int v = p2->m_value;
        cout << p2->m_value;
        while(p2 != NULL && p2->m_value == v)
            p2 = p2->p_next;
        if(p2 == NULL)
            cout<<endl;
        else
            cout<<"->";
    }
}

void createList(List * &Head)
{
    int data;
    cin >> data;
    if(data != 0)
    {
        Head = new List;
        Head->m_value = data;
        Head->p_next = NULL;
        createList(Head->p_next);
    }
}
int main()
{
    List * L1 = NULL;
    List * L2 = NULL;
    createList(L1);
    createList(L2);
    append(L1, L2);

    return 0;
}