链表中倒数第k个结点【微软面试100题第十三题】

题目要求：

　　输入一个链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

　　参考资料：剑指offer第15题

题目分析：

　　1.两个指针，第一个先走k步，然后两个指针同时走，直到第一个走到尾指针，此时第二个指针即为所求；

　　2.令函数原型为：ListNode *findKthToTail(ListNode *head,unsigned int k);

　　　特殊情况：

　　　　　　i).　head为空指针；

　　　　　　ii). head为头结点的链表的结点总数小于k；

　　　　　　iii).k=0.

　　3.注意此处为倒数第0个结点为链表的尾结点，与剑指offer的第一个结点的区别是：第0个结点的最后一个while里应该ptwo->next != NULL；而第1个结点的最后一个while里应该ptwo != NULL。可画图理解。

代码实现：　

#include <iostream>

using namespace std;

typedef struct ListNode

{

    struct ListNode *next;

    int data;

}ListNode;

ListNode *findKthToTail(ListNode *head,unsigned int k);

void initList(ListNode **head);

int main(void)

{

//    int k = 4;

    int k = ;

    ListNode *head;

    initList(&head);

    head = findKthToTail(head,k);

    if(head==NULL)

        cout << "head为空或者链表长度小于k";

    else

        cout << head->data << " ";

    cout << endl;

    return ;

}

ListNode *findKthToTail(ListNode *head,unsigned int k)

{

    if(k== || head==NULL)

        return NULL;

    ListNode *pone,*ptwo;

    pone = ptwo = head;

    for( ; k >  && ptwo != NULL; k--)

        ptwo=ptwo->next;

    if (k > ) return NULL;//链表长度小于k

    while(ptwo->next != NULL)

    {

        pone=pone->next;

        ptwo=ptwo->next;

    }

    return pone;

}

//1-->2-->3-->NULL

void initList(ListNode **head)

{

    ListNode *tmp = new ListNode;

    tmp->data = ;

    *head = tmp;

    tmp = new ListNode;

    tmp->data = ;

    (*head)->next = tmp;

    ListNode *tmp1 = new ListNode;

    tmp1->data = ;

    tmp1->next = NULL;

    tmp->next = tmp1;

}

巴特西

链表中倒数第k个结点【微软面试100题第十三题】

最新文章

热门文章

巴特西

链表中倒数第k个结点 【微软面试100题 第十三题】

最新文章

热门文章

链表中倒数第k个结点【微软面试100题第十三题】