1 求出链表的倒数第K个元素


2 已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序

(保留所有结点，即便大小相同）

在这里使用 两种方法：递归和非递归的方法。


typedef struct node
{
int data;
//Linknode *next; 错误的！！！
struct node *next;
}Linknode;
Linknode *createLink(int n);

======================================================================================

1 求出链表的倒数第K个元素

代码实现：

//定义 node1和node2结点进行比较（相差k-1），当node2到最后的一个结点时，node1即为所求的。
bool findLastKnode( Linknode *head,int numK)
{
assert(head!=NULL);
Linknode *node1,*node2;
node1=head;
node2=head;
int num=1;

//1 找到node2的位置
while(node2!=NULL&&num<numK)
{
num++;
node2=node2->next;
}

//todo：这个判断条件是否需要改进？？？
if(num==numK&&node2!=NULL) //查找成功
{
//while(node2!=NULL)
while(node2->next!=NULL)
{
node1=node1->next;
node2=node2->next;
}
cout<<"找到的结点是："<<node1->data<<endl;
return true;
}
cout<<"I'm sorry,can not find it."<<endl;
return false; //查找失败
}


测试代码：

int num;
cout<<"请输入要创建的节点的个数n：";
cin>>num;
Linknode *link;
link=createLink(num);
bool isFind=findLastKnode(link,2);

return 0;


2 已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序

(保留所有结点，即便大小相同）


注意：下面写的代码里已经假设head1和head2已经排好序了。

2.1 非递归的方法


Linknode * MergeLink( Linknode *head1,Linknode *head2 )
{
    if(head1==NULL)
        return head2;
    if(head2==NULL)
        return head1;
    Linknode *head,*curnode;   //创建的链表的头结点和标识的结点。
    Linknode *link1,*link2;
    link1=head1;
    link2=head2;
    //1 确定头结点
    if(link1->data<=link2->data)
    {
        head=link1;
        link1=link1->next;
    }
    else
    {
        head=link2;
        link1=link2->next;
    }
    cout<<"第一个元素是"<<head->data<<endl;
    //2 循环构建剩下的结点:2.1两个链表都含有节点的时候   2.2 只含有一个节点了。
    curnode=head;
    while(link1!=NULL&&link2!=NULL)
    {
        if(link1->data<=link2->data)
        {
            curnode->next=link1;
            link1=link1->next;
        }
        else
        {
            curnode->next=link2;
            link2=link2->next;
        }
        curnode=curnode->next;         //当前结点往后面移动
    }
    //只含有一个节点的情况
    if(link1!=NULL)
    {
        curnode->next=link1;
    }
    if(link2!=NULL)
    {
        curnode->next=link2;
    }
                                              
    printLink(head);
    return head;
}


2 递归的方法


Linknode * MergeRecursion( Linknode *head1,Linknode *head2 )
{
    //1 最后的退出条件   2 递归：缩小范围或者规模
    if(head1==NULL)
        return head2;
    if(head2==NULL)
        return head1;
    Linknode *head;     //创建的链表的头结点和标识的结点。
    if(head1->data<=head2->data)
    {
        head=head1;
        head->next=MergeRecursion(head1->next,head2);
    }
    else
    {
        head=head2;
        head->next=MergeRecursion(head1,head2->next);
    }
                           
    printLink(head);
    return head;
}


3 代码测试

int main()
{
    int num1,num2;
    cout<<"请输入第一个和第二个链表的个数：";
    cin>>num1>>num2;
    Linknode *link1,*link2,*link;
    link1=createLink(num1);
    link2=createLink(num2);
    //link=MergeLink(link1,link2);
    link=MergeRecursion(link1,link2);
    return 0;
}