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;
}