剑指offer JZ-14

题目描述

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

示例1

输入

复制

1,{1,2,3,4,5}

返回值

复制

{5}

思路：

1.遍历链表，计算链表长度len，倒数第k位是正数len-k+1位，缺点时浪费时间，但是最大时间开销不过2n

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == NULL) return NULL;
        unsigned int len = 0;
        ListNode* pos = pListHead;
        while(pos)
        {
            pos = pos->next;
            len++;
        }
        if(k > len) return NULL;
        k = len-k+1;
        for(unsigned int i=1;i<k;i++)
        {
            if(pListHead)
                pListHead = pListHead->next;
            else
                return NULL;
        }
        return pListHead;
    }
};

2.递归，看起来会优雅一点，但是相对于思路一效率上并未做出优化，好处是面试官会觉得你功力较深（大雾脸）

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    unsigned int count = 0;
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(!pListHead) return NULL;                 //递归边界
        ListNode* temp = FindKthToTail(pListHead->next, k);
        count++;
        if(count == k)                              //回溯时返现了倒数第K位，则返回此时的指针
            return pListHead;
        if(temp)                                    //一旦返回的指针非空，意味着后续转递的指针不应再改变
            return temp;
        return NULL;
    }
};

3.快慢指针，快指针先走k步，而后快指针和慢指针同时前进。快慢指针之间的间隔为K，这样快指针到达终点时，慢指针恰好处于倒数K位。时间开销为链表长度。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(!pListHead) return NULL;
        ListNode* fast = pListHead;
        for(unsigned int i=1;i<=k;i++)
        {
            if(fast)
                fast = fast->next;
            else
                return NULL;
        }
        while(fast)
        {
            pListHead = pListHead->next;
            fast = fast->next;
        }
        return pListHead;
    }
};