鏈表的操作2

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