可視化圖解算法：鏈表中倒數（最后）k個結點

1. 題目

描述

輸入一個長度為 n 的鏈表，設鏈表中的元素的值為ai ，返回該鏈表中倒數第k個節點。

如果該鏈表長度小于k，請返回一個長度為 0 的鏈表。

數據范圍：0≤n≤105，0 ≤ai≤109，0 ≤k≤109

要求：空間復雜度 O(n)，時間復雜度 O(n)

進階：空間復雜度 O(1)，時間復雜度 O(n)

例如輸入{1,2,3,4,5},2時，對應的鏈表結構如下圖所示：

其中藍色部分為該鏈表的最后2個結點，所以返回倒數第2個結點（也即結點值為4的結點）即可，系統會打印后面所有的節點來比較。

示例1

輸入：

{1,2,3,4,5},2

返回值：

{4,5}

說明：

返回倒數第2個節點4，系統會打印后面所有的節點來比較。

示例2

輸入：

{2},8

返回值：

{}

2. 解題思路

獲取鏈表的倒數第K個節點，最先想到的是先獲取鏈表的長度n（共多少個節點，時間復雜度為n），之后再從前向后查找，遍歷n-k個節點。

此題還有一種巧妙的解法：雙指針法。通過此方法可以遍歷一次查找到對應的節點。

假如鏈表結構如下圖所示，給定k=2，即查找倒數第2個節點（值為4的節點）：

這時，可以通過以下步驟完成：

第一步：定義快慢指針。

第二步：移動快指針 k 次（每次移動1個節點）。

k=2，即快指針先移動k次（每次一個節點），這時fast會指向3節點。

第三步：快慢指針一起移動（每次移動1個節點），一直到快指針fast指向Null停下來。

第四步：快指針指向為None，慢指針指向的節點為：倒數第k個節點。

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

Python版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1370264
Java版本：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Java語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1366720
Golang版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364397

3. 編碼實現

3.1 Python編碼實現

class ListNode:def __init__(self, x):self.val = x  # 鏈表的數值域self.next = None  # 鏈表的指針域# 從鏈表節點尾部添加節點
def insert_node(node, value):if node is None:print("node is None")return# 創建一個新節點new_node = ListNode(value)cur = node# 找到鏈表的末尾節點while cur.next is not None:cur = cur.next# 末尾節點的next指針域連接新節點cur.next = new_node# 打印鏈表（從鏈表頭結點開始打印鏈表的值）
def print_node(node):cur = node# 遍歷每一個節點while cur is not None:print(cur.val, end="\t")cur = cur.next  # 更改指針變量的指向print()#
#
# @param pHead ListNode類
# @param k int整型
# @return ListNode類
#
class Solution:def FindKthToTail(self, pHead: ListNode, k: int) -> ListNode:# write code here# 1.  定義快慢指針fast = pHeadslow = pHead# 2. 移動快指針  k 次（每次移動1個節點）for i in range(k):if fast is None:return None  # k大于鏈表長度的情況fast = fast.next# 3. 快慢指針一起移動（每次移動1個節點）while fast is not None:fast = fast.nextslow = slow.next# 4. 快指針指向為None，慢指針指向的節點為：到時候第k個節點return slowif __name__ == '__main__':head = ListNode(1)insert_node(head, 2)insert_node(head, 3)insert_node(head, 4)insert_node(head, 5)print_node(head)s = Solution()node = s.FindKthToTail(head, 2)print(node.val)print_node(node)

3.2 Java編碼實現

package LL08;public class Main {//定義鏈表節點static class ListNode {private int val;  //鏈表的數值域private ListNode next; //鏈表的指針域public ListNode(int data) {this.val = data;this.next = null;}}//添加鏈表節點private static void insertNode(ListNode node, int data) {if (node == null) {return;}//創建一個新節點ListNode newNode = new ListNode(data);ListNode cur = node;//找到鏈表的末尾節點while (cur.next != null) {cur = cur.next;}//末尾節點的next指針域連接新節點cur.next = newNode;}//打印鏈表（從頭節點開始打印鏈表的每一個節點）private static void printNode(ListNode node) {ListNode cur = node;//遍歷每一個節點while (cur != null) {System.out.print(cur.val + "\t");cur = cur.next; //更改指針變量的指向}System.out.println();}public static class Solution {/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** @param pHead ListNode類* @param k     int整型* @return ListNode類*/public ListNode FindKthToTail(ListNode pHead, int k) {// write code here// 1. 定義快慢指針ListNode fast = pHead;ListNode slow = pHead;// 2. 移動快指針 k 次（每次移動1個節點）for (int i = 0; i < k; i++) {if (fast == null) {return null; //k大于鏈表長度的情況}fast = fast.next;}// 3. 快慢指針一起移動（每次移動1個節點）while (fast != null) {fast = fast.next;slow = slow.next;}// 4. 快指針指向為null，慢指針指向的節點為：到時候第k個節點return slow;}}public static void main(String[] args) {ListNode head = new ListNode(1);insertNode(head, 2);insertNode(head, 3);insertNode(head, 4);insertNode(head, 5);printNode(head);Solution solution = new Solution();ListNode node = solution.FindKthToTail(head, 2);System.out.println(node.val);printNode(node);}
}

3.3 Golang編碼實現

package mainimport "fmt"// ListNode 定義鏈表節點
type ListNode struct {Val  int       //鏈表的數值域Next *ListNode //鏈表的指針域
}/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param pHead ListNode類* @param k int整型* @return ListNode類*/
func FindKthToTail(pHead *ListNode, k int) *ListNode {// write code here// 1. 定義快慢指針fast := pHeadslow := pHead// 2. 移動快指針 k 次（每次移動1個節點）for i := 0; i < k; i++ {if fast == nil {return nil //k大于鏈表長度的情況}fast = fast.Next}// 3. 快慢指針一起移動（每次移動1個節點）for fast != nil {fast = fast.Nextslow = slow.Next}// 4. 快指針指向為nil，慢指針指向的節點為：到時候第k個節點return slow
}
func main() {head := ListNode{Val: 1}head.Insert(2)head.Insert(3)head.Insert(4)head.Insert(5)head.Print()node := FindKthToTail(&head, 2)fmt.Println(node.Val)node.Print()
}// Insert 從鏈表節點尾部添加節點
func (ln *ListNode) Insert(val int) {if ln == nil {return}//創建一個新節點newNode := &ListNode{Val: val}cur := ln//找到鏈表的末尾節點for cur.Next != nil {cur = cur.Next}//末尾節點的next指針域連接新節點cur.Next = newNode
}// Print 從鏈表頭結點開始打印鏈表的值
func (ln *ListNode) Print() {if ln == nil {return}cur := ln//遍歷每一個節點for cur != nil {fmt.Print(cur.Val, "\t")cur = cur.Next //更改指針變量的指向}fmt.Println()
}

如果上面的代碼理解的不是很清楚，你可以參考視頻的詳細講解。

Python版本：嗶哩嗶哩_bilibili
Java版本：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili
Golang版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364397

4.小結

獲取鏈表的倒數（最后）第k個節點，可以通過快慢指針快速獲取到：

定義快慢指針。

移動快指針 k 次（每次移動1個節點）。

快慢指針一起移動（每次移動1個節點），一直到快指針fast指向Null停下來。

快指針指向為None，慢指針指向的節點為：倒數第k個節點。

更多算法視頻講解，你可以從以下地址找到：

Python編碼實現：數據結構筆試面試算法-Python語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Python語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1509965
Java編碼實現：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1510007
Golang編碼實現：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1509945