高频面试题之链表专题-查找单链表的倒数第K个节点

以你之姓@ 2022-10-15 14:56 136阅读 0赞

# 2.查找单链表的倒数第K个节点 #

[OJ][][链接：][OJ][https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&rp=2&ru=%2Factivity%2Foj&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey][https_www.nowcoder.com_practice_529d3ae5a407492994ad2a246518148a_tpId_13_tqId_11167_rp_2_ru_2Factivity_2Foj_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking_tab_answerKey]

**高频考察的大厂云图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

### 题目：输入一个链表，输出该链表中倒数第k个结点。 ###

示例1

输入

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

返回值

{5}

### 提供代码 ###

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        
        }
    };

### 解题思路 ###

简单思路：遍历找到未节点并计节点数，数学计算再遍历一次

更优秀解：要求只能遍历链表一次

快慢指针法 fast, slow, 首先让fast先走k步，然后fast,slow同时走，fast走到末尾时，slow走到倒数第k个节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

OJ没有办法很好的调试

考虑极端的情况

或者使用vs快速写int main()然后调试

### **代码实现：** ###

#include<stdio.h>
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };
    class Solution {
    public:
    	ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    		ListNode* slow, * fast;
    		slow = fast = pListHead;
    		//fast先走k步
    		while (k--)//后置--走k次，前置--走k-1次
    		{
    			if (fast == NULL)
    			{
    				// 这里需要注意链表可能没有K步长
    				return NULL;
    			}
    				fast = fast->next;
    		}
    		//同时走，fast为空时，slow指向倒数第k个节点
    		while (fast != NULL)
    		{
    			fast = fast->next;
    			slow = slow->next;
    		}
    		return slow;
    	}
    };
    int main()
    {
    	ListNode* n1 = new ListNode(1);
    	ListNode* n2 = new ListNode(2);
    	ListNode* n3 = new ListNode(3);
    	ListNode* n4 = new ListNode(4);
    	
    	n1->next = n2;
    	n2->next = n3;
    	n3->next = n4;
    	n4->next = NULL;
    
    	Solution().FindKthToTail(n1, 1);
    	return 0;
    }

[OJ]: http://https/www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[https_www.nowcoder.com_practice_529d3ae5a407492994ad2a246518148a_tpId_13_tqId_11167_rp_2_ru_2Factivity_2Foj_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking_tab_answerKey]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&rp=2&ru=%2Factivity%2Foj&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221014/c4a1cd6e107d4bc999cb831e25ef69ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221014/eb1b4c943d1f4032b9e0bdf4adcf4349.png