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

难度简单302收藏分享切换为英文接收动态反馈
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：
给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.

  1. package com.coco.learnalgorithmone.linkedlist;
  3. import com.coco.learnalgorithmone.linkedlist.entity.ListNode;
  4. import com.coco.learnalgorithmone.linkedlist.util.LinkedListUtils;
  6. /**
  7.  * 剑指 Offer 22. 链表中倒数第k个节点
  8.  * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
  9.  *
  10.  * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
  11.  */
  12. public class GetKthFromEnd {
  14.     public static void main(String[] args) {
  15.         int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
  16.         ListNode head = LinkedListUtils.convertToLinkedList(arr);
  17.         System.out.println(getKthFromEnd(head, 3));
  18.     }
  20.     public static ListNode getKthFromEnd(ListNode head, int k) {
  21.         ListNode quick = head;
  22.         ListNode slow = quick;
  24.         for (int i = 1; i < k; i++) {
  25.             quick = head.getNext();
  26.             head = quick;
  27.         }
  29.         while (quick.getNext() != null) {
  30.             quick = quick.getNext();
  31.             slow = slow.getNext();
  32.         }
  34.         return slow;
  35.     }
  37. }