有两个有序链表，各自内部是有序的，但是两个链表之间是无序的

Merge： 1. 写一个Merge函数 2. 如果两个有序链表交叉呢？

合并有序单链表。

struct node{
int data;
node* next;
 };
 typedef node* List;
 List mergeSortedLinkList(List &list1, List &list2)
 {
if (list1 == NULL)
{
    return list2;
}
if (list2 == NULL)
{
    return list1;
}
List pList1 = list1;
List pList2 = list2;
List mergedList = NULL;
if (pList1->data <= pList2->data)
{
    mergedList = pList1;
    pList1 = pList1->next;
}
else
{
    mergedList = pList2;
    pList2 = pList2->next;
}
List pCurNode = mergedList;
while(pList1 && pList2)
{
    if (pList1->data <= pList2->data)
    {
        pCurNode->next = pList1;
        pCurNode = pList1;
        pList1 = pList1->next;
    }
    else
    {
        pCurNode->next = pList2;
        pCurNode = pList2;
        pList2 = pList2->next;
    }
}

if (pList1 != NULL)
{
    pCurNode->next = pList1;
}
if (pList2 != NULL)
{
    pCurNode->next = pList2;
}

return mergedList;
 }

代码我就基于Haitao的来了。 其中VC报错的地方我给修改了。(其实“pCurNode->next = pList1;”这句是没有问题的) 关于交叉也处理了。 以下代码可以通过VC6编译。

typedef struct node{
    int data;
    struct node * next;
}* List;

List mergeSortedLinkList(List list1, List list2)
{
    List pList1,pList2,mergedList,pCurNode;

    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }

    pList1 = list1;
    pList2 = list2;
    mergedList = NULL;
    if (pList1==pList2)
    {       
        mergedList = pList1;
        pList1 = pList1->next;
        pList2 = pList2->next;
    }
    else 
    {
        if (pList1->data <= pList2->data)
        {
            mergedList = pList1;
            pList1 = pList1->next;
        }
        else
        {
            mergedList = pList2;
            pList2 = pList2->next;
        }
    }
    pCurNode = mergedList;
    while(pList1 && pList2)
    {
        if (pList1==pList2)
        {
            pCurNode->next = pList1;
            pCurNode = pList1;
            pList1 = pList1->next;
            pList2 = pList2->next;
        }
        else
        {
            if (pList1->data <= pList2->data)
            {
                pCurNode->next = pList1;
                pCurNode = pList1;
                pList1 = pList1->next;
            }
            else
            {
                pCurNode->next = pList2;
                pCurNode = pList2;
                pList2 = pList2->next;
            }
        }
    }

    pCurNode->next =pList1?pList1:pList2;

    return mergedList;
}