剑指offer-题15：链表中倒数第k个节点

今天药忘吃喽~ 2022-05-30 09:37 112阅读 0赞

## **题目描述** ##

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

实验平台：[牛客网][Link 1]

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

## **解决思路：** ##

![这里写图片描述][70]  
![这里写图片描述][70 1]  
![这里写图片描述][70 2]

另外，我们还需要注意以下会出现的问题，来增强代码的鲁棒性：

1.输入的链表的头结点为null

2.链表的节点总数少于k个

3.输入的参数k为0

针对问题1和3，我们可以返回null;针对问题2，我们可以在循环时进行判断即可，代码如下：

java:

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            if (head == null || k == 0) {
                return null;
            }
            ListNode firstNode = head;
            ListNode secondeNode = null;
    
            for (int i = 0; i < k - 1; i++) {
                if (firstNode.next != null) {
                    firstNode = firstNode.next;
                }else {
                    return null;
                }
            }
    
            secondeNode = head;
            while (firstNode.next != null) {
                firstNode = firstNode.next;
                secondeNode = secondeNode.next;
            }
            return secondeNode;
        }
    }

python:

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution:
        def FindKthToTail(self, head, k):
            # write code here
            if head is None or k == 0:
                return None
            first_node = head
            for i in range(0, k-1):
                if first_node.next is not  None:
                    first_node = first_node.next
                else:
                    return None
            second_node = head
            while first_node.next is not None:
                first_node = first_node.next
                second_node = second_node.next
            return second_node

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220530/22d884ee6034419ca6e7789b0059d87e.png
[70 1]: /images/20220530/8dc98d3ca05c4175bb3ec163efe5e0b9.png
[70 2]: /images/20220530/930a091cc474471d91db0b730d045bd0.png