【链表OJ题 3】链表中倒数第k个结点

女爷i 2023-09-27 19:26 126阅读 0赞

**目录**

题目来源：

代码实现：

思路分析：

错误分析：

--------------------

## 题目来源： ##

[链表中倒数第k个结点\_牛客题霸\_牛客网 (nowcoder.com)][k_ _nowcoder.com]

**题目描述：**

![4dde8c23eac42516cbe52c97de8630fa.png][]

## 代码实现： ##

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
        // write code here
        struct ListNode* slow = pListHead, *fast = pListHead;
    
        while(k--)
        {
            //k大于链表的长度
            if(fast == NULL)
                return NULL;
            
            fast = fast->next;
        }
    
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        return slow;
    }

### 思路分析： ###

![9af1f469955efb44985b34ba67ec6e58.png][]

我们让 fast 先走 k 步，然后 slow 与 fast 再一起走，每次分别走一步，当fast 为 NULL 的时候，slow就指向倒数第 k 个结点。

![43e12401fff5baa262de0ae1de857bc9.png][]

#### 错误分析： ####

我们将用例都测试一下：

![41b98caa86fd7a9ac7dc3ae78c142e56.png][]

第一组成功，我们继续测第二组

![7e8b24f08a0b520be2c0ca8bfefc1086.png][]

这个看这个用例，链表为空的时候，我们要找倒数第100个结点，这个结点是不存在的，应该返回NULL，但是我们却让 fast 先走100步，链表本就是空，fast只要走就会导致空指针异常，所以我们写的代码就会漏洞。我们应该在 fast = fast->next 前就先判断 fast 是否为空，这样也就判断了链表不为空，但是链表的长度小于 k 这样的情况。

![e02c7baea0791a182b7df1a2a7ca8e8e.png][]

![0e0d3f4b0927c9fc6b5cde08b47f7c36.png][]

\*\*\* 本篇结束 \*\*\*

[k_ _nowcoder.com]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[4dde8c23eac42516cbe52c97de8630fa.png]: https://img-blog.csdnimg.cn/img_convert/4dde8c23eac42516cbe52c97de8630fa.png
[9af1f469955efb44985b34ba67ec6e58.png]: https://img-blog.csdnimg.cn/img_convert/9af1f469955efb44985b34ba67ec6e58.png
[43e12401fff5baa262de0ae1de857bc9.png]: https://img-blog.csdnimg.cn/img_convert/43e12401fff5baa262de0ae1de857bc9.png
[41b98caa86fd7a9ac7dc3ae78c142e56.png]: https://img-blog.csdnimg.cn/img_convert/41b98caa86fd7a9ac7dc3ae78c142e56.png
[7e8b24f08a0b520be2c0ca8bfefc1086.png]: https://img-blog.csdnimg.cn/img_convert/7e8b24f08a0b520be2c0ca8bfefc1086.png
[e02c7baea0791a182b7df1a2a7ca8e8e.png]: https://img-blog.csdnimg.cn/img_convert/e02c7baea0791a182b7df1a2a7ca8e8e.png
[0e0d3f4b0927c9fc6b5cde08b47f7c36.png]: https://img-blog.csdnimg.cn/img_convert/0e0d3f4b0927c9fc6b5cde08b47f7c36.png