剑指 Offer 22. 链表中倒数第k个节点

https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

解法一： 顺序遍历

首先统计链表中有多少节点n，然后倒数第k节点是顺数第一n-k 1个节点

class Solution { 
            public ListNode getKthFromEnd(ListNode head, int k) { 
                int n=0;         ListNode cur=head;         while(cur!=null){ 
                    n ;             cur=cur.next;         }         cur=head;         int i=0;         while(i<n-k){ 
                    cur=cur.next;             i ;         }         return cur;     } } //O(n) //O(1) 

解法二:指针快慢

先让快指针先走k步，然后快慢指针一起走。当快指针结束时，慢指针正好到达倒数第k节点

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