【LeetCode 剑指 Offer 22. 链表中倒数第k个节点(简单)】

输入链表，输出链表中倒数第K节点。为了满足大多数人的习惯，这个问题从1开始计数，即链表的尾节点是倒数第一节点。

例如，链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。链表倒数第二 3 节点值为 4 的节点。

示例：

给定一个链表： 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof 作权归网络所有。商业转载请联系官方授权，非商业转载请注明出处。

双指针

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { 
             public ListNode getKthFromEnd(ListNode head, int k) { 
                 if(head==null)             return null;         ListNode first=head,second=head;         int len=0;         while(first.next!=null){ 
                     len ;             first = first.next;         }         while(len-k 1>0){ 
                     second = second.next;             len--;         }         return second;     } } 

单指针

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { 
             public ListNode getKthFromEnd(ListNode head, int k) { 
                if(head==null)             return null;
        ListNode cur=head;
        while(cur!=null){ 
        
            cur = cur.next;
            if(k==0)
                head = head.next;
            else
                k--;
        }
        return head;
    }
}