[数据结构与算法]链表中倒数第k个结点

链接
描述
输入一个链表，输出该链表中倒数第k个结点。
示例1
输入：
1,{1,2,3,4,5}
复制
返回值：
{5}

长度法

首先计算出整个链表的长度，其次根据K的值做差，最后重新遍历链表，找到相应位置的值。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* head=pListHead;
    int i=0;
    while(head)
    {
        i++;
        head=head->next;
    }
    i=i-k;
    if(i>=0)
    { 
        while(i--)
        {
            pListHead=pListHead->next;
        }
         return pListHead;
     }
     else
     {
         return 0;
     }
}

双指针法

定义两个指针分别指向链表的头根据K的值，让其中的一个先走K个单位，最后两个指针分别往前直至，链表为空取对应的值即为所需要的值。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
   struct ListNode* fast=pListHead;
   struct ListNode* slow=pListHead;
    while(k--)
    {
        if(fast)
        {
            fast=fast->next;
        }
        else
        {
            return 0;
        }
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}