剑指Offer—编程题15（链表中倒数第k个结点）

本文主要是介绍剑指Offer—编程题15（链表中倒数第k个结点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：输入一个链表，输出该链表中倒数第k 个结点．为了符合大多数人的习惯，本题从1 开始计数，即链表的尾结点是倒数第1 个结点．例如一个链表有6 个结点，从头结点开始它们的值依次是1 、2、3、4、5 、6。这个个链表的倒数第3 个结点是值为4 的结点．

public static class ListNode {int value;ListNode next;
}

解题思路：

为了实现只遍历链表一次就能找到倒数第k 个结点，我们可以定义两
个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k 步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1 ，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k 个结点。

代码实现：

public class Test15 {public static class ListNode {int value;ListNode next;}/*** 输入一个键表，输出该链表中倒数第k 个结点．为了符合大多数人的习惯，* 本题从1开始计数，即链表的尾结点是倒数第1个结点．例如一个链表有6个结点，* 从头结点开始它们的值依次是1、2、3、4、5 6。这个链表的倒数第3个结点是值为4的结点．** @param head 链表的头结点* @param k    倒数第k个结点* @return 倒数第k个结点*/public static ListNode findKthToTail(ListNode head, int k) {// 输入的链表不能为空，并且k大于0if (k < 1 || head == null) {return null;}// 指向头结点ListNode pointer = head;// 倒数第k个结点与倒数第一个结点相隔k-1个位置// pointer先走k-1个位置for (int i = 1; i < k; i++) {// 说明还有结点if (pointer.next != null) {pointer = pointer.next;}// 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素else {// 返回结果return null;}}// pointer还没有走到链表的末尾，那么pointer和head一起走，// 当pointer走到最后一个结点即，pointer.next=null时，head就是倒数第k个结点while (pointer.next != null) {head = head.next;pointer = pointer.next;}// 返回结果return head;}public static void main(String[] args) {ListNode head = new ListNode();head.value = 1;head.next = new ListNode();head.next.value = 2;head.next.next = new ListNode();head.next.next.value = 3;head.next.next.next = new ListNode();head.next.next.next.value = 4;head.next.next.next.next = new ListNode();head.next.next.next.next.value = 5;head.next.next.next.next.next = new ListNode();head.next.next.next.next.next.value = 6;head.next.next.next.next.next.next = new ListNode();head.next.next.next.next.next.next.value = 7;head.next.next.next.next.next.next.next = new ListNode();head.next.next.next.next.next.next.next.value = 8;head.next.next.next.next.next.next.next.next = new ListNode();head.next.next.next.next.next.next.next.next.value = 9;System.out.println(findKthToTail(head, 1).value); // 倒数第一个System.out.println(findKthToTail(head, 5).value); // 中间的一个System.out.println(findKthToTail(head, 9).value); // 倒数最后一个就是顺数第一个System.out.println(findKthToTail(head, 10));}
}

这里写图片描述