面试题15:链表中倒数第K个节点

题目:输入一个链表,输出该链表中倒数第K个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第一个节点。

链表的定义如下:


struct ListNode{
    int value;
    ListNode* next;
    ListNode(int data=int()):value(data),next(NULL)
    {}
};

分析

有三种方法:递归法,自定义栈法和前后指针法。

递归法

代码如下:


ListNode* _FindKthToTail(ListNode* head,int& k)
{
    if(head==NULL)
    {
        return  NULL;
    }
    else
    {
        ListNode* tmp=_FindKthToTail(head->next,k);
        if(k==0)
            return tmp;
    }
    if(k==1)
    {
        k=0;
        return head;
    }
    else if(k>1)
        k--;
}

ListNode* FindKthToTail(ListNode* head,int k)throw(ListIsTooShort)
{
    ListNode* tmp=_FindKthToTail(head,k);
    if(k==0)
        return tmp;
    else
        throw ListIsTooShort();
}

自定义栈法


ListNode* FindKthToTail(ListNode* head,int k)throw(ListIsTooShort)
{
    if(head==NULL || k<=0)
        return NULL;
    stack<ListNode*> s;
    while(head!=NULL)
    {
        s.push(head);
        head=head->next;
    }
    while(--k!=0 && !s.empty())
    {
        s.pop();
    }
    if(k==0)
        return s.top();
    else
        throw ListIsTooShort();
}

前后指针法


ListNode* FindKthToTail(ListNode* head,int k)throw(ListIsTooShort)
{
    if(head==NULL || k==0)
        return NULL;
    ListNode* front=head,*last=head;
    while(k-->0 && front!=NULL)
    {
        front=front->next;
    }
    if(k>0)
    {
        throw ListIsTooShort();
    }
    else
    {
        while(front!=NULL)
        {
            front=front->next;
            last=last->next;
        }
    }
    return last;
}

这三种方法的优缺点如下:

时间复杂度 空间复杂度 是否最优
**递归法** O(n) O(n)
**自定义栈法** O(n) O(n)
**前后指针法** O(n) O(1)

因此,最好的方法是最后一种。

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往