当前位置:编程学习 > C/C++ >>

微软等数据结构与算法面试100题 第十三题

第十三题
题目:输入一个单向链表,输出该链表中倒数第k个结点。

这道题比较简单,就是对于这个链表,定义两个指针head1 head2,然后让head1向前走k-1个位置以后,head2和head1同时向前走,知道head1知道NULL指针,head2的即为倒数第k个指针。

代码:
[cpp] 
#include<iostream> 
using namespace std; 
 
 
typedef struct node 

    node * nodeNext; 
    int value; 
}node; 
 
int seekReListK(node *head, int k) 

    if(NULL==head) 
    { 
        cout<<"空链表"; 
        return -1; 
    } 
    node *head1 = head; 
    node *head2 = head; 
    k = k - 1; 
    while(k) 
    { 
        k = k - 1; 
        if(NULL!=head1 ->nodeNext) 
            head1 = head1 ->nodeNext; 
        else 
        { 
            cout<<"K超过链表的长度"<<endl; 
            return -1; 
        } 
    } 
    //现在head1比head2快k个 
    while(NULL!=head1->nodeNext) 
    { 
        head1 = head1->nodeNext; 
        head2 = head2->nodeNext; 
    } 
      
    return head2->value; 

int main() 

    //构建链表 
    node *a = new struct node(); 
    node *b = new struct node(); 
    node *c = new struct node(); 
    node *d = new struct node(); 
    node *e = new struct node(); 
    node *f = new struct node(); 
    node *g = new struct node(); 
    node *h = new struct node(); 
    node *i = new struct node(); 
    node *j = new struct node(); 
    a->nodeNext = b; 
    b->nodeNext = c; 
    c->nodeNext = d; 
    d->nodeNext = e; 
    e->nodeNext = f; 
    f->nodeNext = g; 
    g->nodeNext = h; 
    h->nodeNext = i; 
    i->nodeNext = j; 
    j->nodeNext = NULL; 
    a->value = 0; 
    b->value = 1; 
    c->value = 2; 
    d->value = 3; 
    e->value = 4; 
    f->value = 5; 
    g->value = 6; 
    h->value = 7; 
    i->value = 8; 
    j->value = 9; 
 
    cout<<seekReListK(a,1)<<endl; 
    cout<<seekReListK(a,10)<<endl; 
    cout<<seekReListK(a,11)<<endl; 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,