刷题笔记:返回链表中倒数第k个节点

刷题笔记:返回链表中倒数第k个节点

basic method:快慢指针法

标注解答:

思路分析:

使用快慢双指针:

快指针fast,先走k步,在这里做一个解释:

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

相当于:

while(k > 0){

fast = fast.next;

k--;

}//走三步:先走再减

如果:

while(--k> 0){
fast = fast.next;

}//走两步:先减再走

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (k-- > 0) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

作者：AC_OIer
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/gong-shui-san-xie-yi-ti-san-jie-zhan-dui-w3rz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的解答:

class Solution {

    public ListNode getKthFromEnd(ListNode head, int k) {

       ListNode pre = head;

       ListNode cur = head;

       while(cur != null){

       if(k > 0){

           cur = cur.next;

           k--;

       }

       else{

        pre = pre.next;

        cur = cur.next;             

       }

    }

    return pre;

    }

}