////  main.cpp//  combineSortedList////  Created by Hugo Cao  on 15/7/8.//  Copyright (c) 2015年 Hugo Cao . All rights reserved.///* 题目：合并两个排序的链表 输入两个递增排序的链表， 合并这两个链表并使链表中的结点仍然是按照递增顺序排列的，  例如 1 3 5 7 2 4 6 8. 测试数据：需要添加 null链表 和 相等的链表   */#include 
     
      using namespace std;typedef struct ListNode {    int m_value;    ListNode *m_pnext;} ListNod, *LNode;//添加结点LNode addlistNode(int value){    LNode pNode = new ListNod();    if (pNode == NULL)    {        cout << "申请失败" << endl;        return NULL;    }    pNode->m_value = value;    pNode->m_pnext = NULL;        return pNode;}//链接节点void connectList(LNode point1, LNode point2){    if (point1 != NULL && point2 != NULL)        point1->m_pnext = point2;}//创建链表LNode createListOne(){    LNode p1 = addlistNode(1);    LNode p2 = addlistNode(3);    LNode p3 = addlistNode(5);    LNode p4 = addlistNode(7);        connectList(p1, p2);    connectList(p2, p3);    connectList(p3, p4);        return p1;}LNode createListTwo(){    LNode p1 = NULL;//    LNode p1 = addlistNode(1);//    LNode p2 = addlistNode(3);//    LNode p3 = addlistNode(5);//    LNode p4 = addlistNode(7);//    //    connectList(p1, p2);//    connectList(p2, p3);//    connectList(p3, p4);        return p1;}//输出列表void printList(LNode head){    cout << "========" << endl;    if (head == NULL)    {        cout << "is empty" << endl;        return ;    }        LNode p1 = head;    while (p1 != NULL) {        cout << p1->m_value << " ";        p1 = p1->m_pnext;    }        cout << endl;}//合并两个排序列表LNode combineSortList(LNode p1, LNode p2){    if (p1 == NULL && p2 == NULL)       // 两个链表都为空    {        cout << "链表都为空，无需排序" << endl;        return NULL;    }    if (p1 == NULL && p2 != NULL)       // 其中一个为空    {        return p2;    }    if (p1 != NULL && p2 == NULL)    {        return p1;    }        LNode head = NULL, point = NULL;    //头结点和链接结点    while (p1 != NULL && p2 != NULL)    {        //如果2个链表出现了相同的数字，就去掉一个        if (p1->m_value == p2->m_value)        {            LNode fp = p1;            p1 = p1->m_pnext;            delete fp;        }        //p1,p2都不为空，如果p1 > p2.        if ((p1 != NULL && p2 != NULL) && (p1->m_value > p2->m_value))        {            if (point == NULL)      //当point为空时，就是头结点            {                point = p2;                head = point;            }            else            {                point->m_pnext = p2;                point = p2;            }                        p2 = p2->m_pnext;                    }        if ((p1 != NULL && p2 != NULL) && (p1->m_value < p2->m_value))        {            if (point == NULL)      //当point为空时，就是头结点            {                point = p1;                head = point;            }            else            {                point->m_pnext = p1;                point = p1;            }                        p1 = p1->m_pnext;        }    }        //判断是否有剩余结点，余下全部连接。    if (p1 == NULL && p2 != NULL)    {        point->m_pnext = p2;    }    else if (p2 == NULL && p1 != NULL)    {        point->m_pnext = p1;    }        return head;}int main(){        LNode p1 = createListOne();    LNode p2 = createListTwo();        printList(p1);    printList(p2);        cout << "合并" << endl;        LNode head = combineSortList(p1, p2);    printList(head);        return 0;}