程序员面试金典2.2 链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

class Solution {

public:

    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {

        if(pListHead==NULL||k==0)

            return NULL;

        ListNode*pTail=pListHead,*pHead=pListHead;

//链表指针，pHead,pTail。 pHead先走k-1步，然后，pHead和pTail同时后移，

//等走到链表末尾时，pTail的位置就是倒数第k个节点。

        for(int i=1;i<k;++i)

        {

            if(pHead->next!=NULL)

                pHead=pHead->next;

            else

                return NULL;

        }

        while(pHead->next!=NULL)

        {

            pHead=pHead->next;

            pTail=pTail->next;

        }

        return pTail;

    }

};










使用Stack，将结点压入栈中，再取出第k个就好

if(head == null || k ==0 ){

            return null;

        }

         

        //可以先把链表反转，然后找出第k个

        Stack<ListNode> stack = new Stack<ListNode>();

        int count = 0;

        while(head != null){

            stack.push(head);

            head = head.next;

            count++;

        }

         

        if(count < k){

            return null;

        }

         

        ListNode knode = null;

        for(int i = 0; i < k; i++){

            knode = stack.pop();

        }

         

         

        return knode;