剑指offer14

剑指offer14：链表中倒数第K个结点

题目描述

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

解法一：基于递归的方法

class Solution {
public:
    unsigned int cnt = 0;
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL)
            return NULL;
        ListNode* node = FindKthToTail(pListHead->next, k);
        if (node != NULL)
            return node;
        cnt++;
        if (cnt == k)
            return pListHead;
        else
            return NULL;
    }
};

解法二：基于正数第i-k个

class Solution2 {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL || k == 0)
            return NULL;
        ListNode* flag = pListHead;
        ListNode* first = pListHead;
        unsigned int i = 1;
        while (flag->next != NULL)
        {
            flag = flag->next;
            i++;
        }
        unsigned int j = 1;
        if (i<k)
            return NULL;
        else
        {
            for (j = 1; j <= (i - k); j++)  //倒数第k个则是正数第i-k个，一共有i个
                first = first->next;
            return first;
        }
    }
};

解法三：基于快慢双指针

class Solution3 {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL || k == 0)
            return NULL;
        ListNode*pTail = pListHead, *pHead = pListHead;
        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;
    }
};