算法填空：A，B为升序的带头结点的单链表，将B合并到A中。

链表:A ->1->2->3
链表:B ->3->4->5
合并A和B，并把B中重复的结点释放。

结果：A->1->2->3->4->5。



typedef struct node {
        int data;
        struct node *next;
        }linknode, *link;
       

void union(link A, link B)
{
        link q,p,p1,u;
       
        q=B->next;
        free(B);
        p1=A->next;
       
        while(_________________)
        {
                p=p1;
               
                while(_____________)
                {
                        p=p->next;
                }
               
                if(___________)
                {
                        u=q->next;
                        ___________;
                        ___________;
                        q=u;
                }
                else
                {
                        u=q;
                        ________;
                        free(u);
                }
        }
}

那么，至此为止#32楼的coding3215的答案好象是唯一的解，解题的思路是：
BEGIN
1。循环B链表。
2。查找B中是否有A的重复节点
2.1如有，则释放B的重复节点。
2.2.1如无重复，则找到插入位置的前节点
2.2.2插入节点。
END

填空答案为：
1。q
2。 p && q->data != p->data
3。!p
4。for (p = A; p->next && p->next->data < q->data; p = p->next);
5。 q->next = p->next, p->next = q;
6。q = q->next;
还有没有其它的方法呢？从程序的其它语句中来看，主要是把人的思路引导到这个结果上来，但还是有点忐忑第四和第五个空儿。

还有可能有多的答案吗？

[ 本帖最后由 liuboo 于 2008-6-27 16:22 编辑 ]

q=p->next;

？？？

有问题吧……
未初始化的指针就敢用啊

这个算法想了很久也没有想通。这儿的两个while的循环如何确定呢？ 第二个while要是什么做条件，才要移动p=p->next?
接下来的if又是以什么条件来判断呢？

我理解的大概意思是，要将B中的结点接到A中，把B中重复的结点释放。可是照着这么想，那六个空却无法填上正确的语句~~


想不明白这个算法~~

还望高人指点一二，谢谢？

是q=B->next;吧

对，是q=B->next.

大家帮忙想想吧~我真的是想不出来结果了？（怀疑智商了。。。。。）


那两个while和一个if到底的逻辑是什么？

[ 本帖最后由 liuboo 于 2008-6-26 10:43 编辑 ]

no one can help it?

哪来的题目？小到函数也要有一个明确的规格吧，这里显然没说清楚：
1. 合并以后是什么样的，把B的节点全部导到A中，而B为空，还是反之？
2. 是不是链表中不能出现相同的节点？排序并不隐含这一条件。

从代码看释放了B，我们假设是由A带出的，那么代码中存在一个基本的问题：如果B->next的值小于A->next，上述代码能修改A->next吗？p1是A->next的值，而不是这自身。

链表:A ->1->2->3
链表:B ->3->4->5
合并A和B，并把B中重复的结点释放。

结果：A->1->2->3->4->5。

很多笔试都出这个题

void union(link A, link B)
{
        link q,p,p1,u;
      
        q=B->next;
        free(B);
        p1=A->next;
      
        while(q)
        {
                p=p1;
               
                while( p && q->data != p->data )//查找B中是否有A的重复节点
                {
                        p=p->next;
                }
               
                if(!p)  //没有找到重复节点，连接到A表的相应位置
                {
                        u=q->next;
                        //找到插入位置的前节点
                        for (p = A; p->next && p->next->data < q->data; p = p->next);
                        //插入到合适的位置
                        q->next = p->next, p->next = q;                                                                          
                        q=u;
                }
                else//找到重复节点，删除之
                {
                        u=q;
                        q = q->next;
                        free(u);
                }
        }
}

[ 本帖最后由 coding3125 于 2008-6-27 11:27 编辑 ]