合并两个有序链表

面试中遇到了道题！合并两个有序链表

贴贴代码！

#include <iostream>

using namespace std;
struct linkNode
{
    int element;
    linkNode *next;
};

linkNode * getLink(linkNode *firstLink,linkNode *secondLink)
{
    if(firstLink->element <= secondLink->element) {
         linkNode * head = firstLink;
         while(firstLink->element <= secondLink->element)
         {
             if(firstLink->next != NULL)
             {
                  if(firstLink->next->element > secondLink->element)
                  {
                     linkNode * tmp = firstLink->next;
                     firstLink->next = secondLink;
                     secondLink = secondLink->next;
                     firstLink->next->next = tmp;
                     if(secondLink == NULL) {
                         break;
                     }
                  }
                  firstLink = firstLink->next;
             }
             else
             {
                  firstLink->next = secondLink;
                  break;
             }

         }
         return head;
    }else {
        return getLink(secondLink,firstLink);
    }
}

void print(linkNode * node)//用于打印链表
{
    while(node->next != NULL)
    {
        cout << node->element << " ";
        node = node->next;
    }
    cout << node->element << "";
}

linkNode * buildLink(int array[],int size)
{
    linkNode * link = new linkNode();
    link->element = array[0];
    linkNode * tmplink = link;
    for(int i = 1 ; i < size ; i ++)
    {
        linkNode * tmp = new linkNode();
        tmp->element = array[i];
        tmplink->next = tmp;
        tmplink = tmplink->next;
    }
    return link;
}

int main()
{
    //初始化链表（有序）
    int a [] = {1,4,5,10,10};
    int b [] = {1,2,5,7};

    linkNode * firstLink = buildLink(a,5);

    linkNode * secondLink = buildLink(b,4);

    //显示

    print(firstLink);
    cout << endl;
    print(secondLink);
    //合并
    cout << endl;
    linkNode *newLink = getLink(firstLink,secondLink);
    print(newLink);
    cout << endl;
    return 0;
}

 

 

评论

5 楼 小羊fc 2012-10-11  

liuInsect 写道

小羊fc 写道

liuInsect 写道

“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊？ 如果第一个链表的元素都大于第二个链表，
就直接返回第一个链表？

这个情况确实没想好！我改改！

思路是， 一定要把第一个链表遍历完 在遍历的时候与第二个链表比 来确定谁放在但当前位置。
直到第一个链表结束 若第二个链表还有元素 全部copy就行。

我按的似乎是这个思路呀！

4 楼 小羊fc 2012-10-11  

liuInsect 写道

“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊？ 如果第一个链表的元素都大于第二个链表，
就直接返回第一个链表？

改好了，谢谢你帮我指出错误，那种情况应该可以解决了！

3 楼 liuInsect 2012-10-11  

小羊fc 写道

liuInsect 写道

“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊？ 如果第一个链表的元素都大于第二个链表，
就直接返回第一个链表？

这个情况确实没想好！我改改！

思路是， 一定要把第一个链表遍历完 在遍历的时候与第二个链表比 来确定谁放在但当前位置。
直到第一个链表结束 若第二个链表还有元素 全部copy就行。

2 楼 小羊fc 2012-10-11  

liuInsect 写道

“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊？ 如果第一个链表的元素都大于第二个链表，
就直接返回第一个链表？

这个情况确实没想好！我改改！

1 楼 liuInsect 2012-10-11  

“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊？ 如果第一个链表的元素都大于第二个链表，
就直接返回第一个链表？