[LeetCode]面试题 02.02. 返回倒数第 k 个节点

算法标签 双指针 链表

题目简叙

思路

快慢指针的方式
使用两个初始指针指向头部
指针a向后移动K个位置
从现在开始ab指针都向后移动到底
此时b移动了len-a的长度
这样b就移动到了len-a的位置即相当于移动到了倒数第K个位置

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
       ListNode* low=head;
       ListNode* fast = head;

       while(k--)fast=fast->next;

       while(fast)fast=fast->next,low=low->next;

       return low->val; 
    }
};

AC记录