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

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2 输出： 4 说明：

给定的 k 保证是有效的。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

  • 此题与 题目19 基本一样
  • 利用快慢指针思想
  • 开始快慢指针都指向head
  • 快指针往前走k步时，慢指针开始走
  • 当快指针指向null时，慢指针就指向第k个节点
  • 然后把 慢指针的val返回即可

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

 public int kthToLast(ListNode head , int k){

        if (head.next == null) return head.val;

        ListNode fast = head;
        ListNode slow = head;

        int step = 0;
        while (fast != null){

            if (step >= k) slow = slow.next;
            fast = fast.next;
            step ++;
        }

        return slow.val;
    }