題目來(lái)源：牛客網(wǎng)-劍指Offer專題
題目地址：鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

題目描述

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

節(jié)點(diǎn)結(jié)構(gòu)如下：

public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;} }

題目解析

這是一道和鏈表相關(guān)的題，對(duì)于這種題目，在熟悉鏈表的基本操作解決基本問(wèn)題之余，也一定要記得處理空指針之類的有可能造成程序異常終止的情況，不要貪圖方便（尤其是那些前競(jìng)賽選手 ）。

方法一：
這是一種最常規(guī)的方法，先遍歷一次鏈表求出鏈表的的長(zhǎng)度 $len$，然后將倒數(shù)第 k 個(gè)節(jié)點(diǎn)轉(zhuǎn)換為順數(shù)第len-k個(gè)節(jié)點(diǎn)，最后第二次遍歷去求解即可。

public class Solution {public ListNode FindKthToTail(ListNode head, int k) {if (head == null || k < 1)return null;int len = 0, i = 0;//計(jì)算鏈表長(zhǎng)度ListNode p = head;while (p != null) {p = p.next;len++;}//如果k比len還大，就直接返回nullif (k > len) {return null;}//找倒數(shù)第k個(gè)節(jié)點(diǎn)（其實(shí)就是順數(shù)第len-k個(gè)節(jié)點(diǎn)）p = head;while (i < len - k) {p = p.next;i++;}return p;} }

方法二：
其實(shí)我們只需要進(jìn)行一次遍歷操作就可以求出需要的答案，網(wǎng)上很多人把這個(gè)稱之為“快慢指針?lè)ā?#xff0c;即讓慢指針在快指針移動(dòng) $k$ 個(gè)節(jié)點(diǎn)后再開(kāi)始移動(dòng)，當(dāng)快指針移動(dòng)到鏈表末尾(null)時(shí)，慢指針就到達(dá)了倒數(shù) $k$ 個(gè)節(jié)點(diǎn)。

聽(tīng)起來(lái)有點(diǎn)玄乎？請(qǐng)聽(tīng)我細(xì)細(xì)道來(lái)~

如下圖所示，由于我們最后到達(dá)的是末端(null)，那我們就從末端開(kāi)始移動(dòng) $k$ 個(gè)節(jié)點(diǎn)，就到達(dá)了我們的倒數(shù)第 $k$ 個(gè)節(jié)點(diǎn)，也就是我們的目標(biāo) $target$。最后再?gòu)?$target$ 移動(dòng)到慢指針 $slow$ 的位置。

現(xiàn)在，我們把部分過(guò)程逆轉(zhuǎn)過(guò)來(lái)，我們要從 $slow$ 移動(dòng)到慢指針 $target$ 的位置。問(wèn)題是我們又不知道要移動(dòng)多少個(gè)節(jié)點(diǎn)，暫時(shí)設(shè)為 $x$ ，于是有
$$x+k=len$$
我們讓快指針先移動(dòng)了 $k$ 個(gè)節(jié)點(diǎn)，再讓慢指針和快指針一起移動(dòng)，實(shí)際上就是用快指針去度量鏈表的長(zhǎng)度 $len$，將慢指針移動(dòng)的距離限定為 $x=len?k$ 個(gè)節(jié)點(diǎn)。

public class Solution {public ListNode FindKthToTail(ListNode head, int k) {if (head == null || k < 1)return null;ListNode p, q;p = q = head;int i = 0;for (; p != null; i++) {if (i >= k) {//快指針移動(dòng)了k個(gè)節(jié)點(diǎn)后，慢指針開(kāi)始移動(dòng)q = q.next;}//快指針需要一直移動(dòng)p = p.next;}return i < k ? null : q;} }

---

本文為原創(chuàng)，作者博客地址為：Veggie的博客
如果本文對(duì)你有所幫助，要記得點(diǎn)贊哦~

總結(jié)

以上是生活随笔為你收集整理的剑指Offer #14 链表中倒数第k个结点（快慢指针） | 图文详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。