牛客网高频算法题系列-BM8-链表中倒数最后k个结点

题目描述

描述：输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。

原题目见：BM8 链表中倒数最后k个结点

解法一：双指针法

首先，考虑两种特殊情况：

  • 如果原链表为空，直接返回null。
  • 如果k不是正数，直接返回null。

否则，使用双指针求解，求解过程如下：

  • 首先，遍历链表，将fast结点指向第k个结点；
  • 如果遍历完后fast为null，说明链表长度小于k，不存在倒数第k个结点，直接返回null；
  • 否则，快慢指针一起移动，直到fast移动到最后一个结点，此时，slow即为倒数第k个结点，返回之。

代码

  1. public class Bm008 {
  2.     /**
  3.      * 链表中倒数最后k个结点
  4.      *
  5.      * @param pHead ListNode类
  6.      * @param k     int整型
  7.      * @return ListNode类
  8.      */
  9.     public static ListNode findKthToTail(ListNode pHead, int k) {
  10.         // 如果原链表为空，直接返回null
  11.         if (pHead == null) {
  12.             return null;
  13.         }
  14.         // 如果k不是正数，直接返回null
  15.         if (k <= 0) {
  16.             return null;
  17.         }
  18.         ListNode fast = pHead;
  19.         // 将fast结点指向第k个结点
  20.         for (int i = 0; i < k - 1 && fast != null; i++) {
  21.             fast = fast.next;
  22.         }
  23.         // 如果fast为null，说明链表长度小于k，不存在倒数第k个结点，直接返回null
  24.         if (fast == null) {
  25.             return null;
  26.         }
  28.         ListNode slow = pHead;
  29.         // 快慢指针一起移动，直到fast移动到最后一个结点，此时，slow即为倒数第k个结点
  30.         while (fast.next != null) {
  31.             slow = slow.next;
  32.             fast = fast.next;
  33.         }
  35.         return slow;
  36.     }
  38.     public static void main(String[] args) {
  39.         ListNode pHead = ListNode.testCase2();
  40.         System.out.println("原链表为");
  41.         ListNode.print(pHead);
  42.         int k = 2;
  43.         System.out.println("链表中的倒数第" + k + "个结点为：");
  44.         System.out.println(findKthToTail(pHead, k));
  45.     }
  46. }

牛客网高频算法题系列-BM8-链表中倒数最后k个结点 - 图1
牛客网高频算法题系列-BM8-链表中倒数最后k个结点 - 图2
相信坚持的力量！