题目描述

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

注意：

• k >= 0;
• 如果k大于链表长度，则返回 NULL;

样例

输入：链表：1->2->3->4->5 ，k=2

输出：4

算法

(链表) $O(n)$

由于单链表不能索引到前驱节点，所以只能从前往后遍历。

我们一共遍历两次：

1. 第一次遍历得到链表总长度 $n$；
   链表的倒数第 $k$ 个节点，相当于正数第 $n-k+1$ 个节点。所以第二次遍历到第 $n-k+1$ 个节点，就是我们要找的答案。
   注意当 $k>n$ 时要返回nullptr。

时间复杂度

链表总共遍历两次，所以时间复杂度是 $O(n)$。

参考文献

yxc大神的题解

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        int length=0;
        auto p=pListHead;
        while(p!=NULL){
            p=p->next;
            length++;
        }
        if(k>length)return NULL;
        for(int i=0;i<length-k;i++)pListHead=pListHead->next;
        return pListHead;
    }
};

C 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 * 
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct ListNode* findKthToTail(struct ListNode* pListHead, int k) {
    int length=0;
    struct ListNode*p=pListHead;
    while(p!=NULL){
        p=p->next;
        length++;
    }
    if(k>length)return NULL;
    for(int i=0;i<length-k;i++)pListHead=pListHead->next;
    return pListHead;
}

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode findKthToTail(ListNode pListHead, int k) {
        int length=0;
        ListNode p=pListHead;
        while(p!=null){
            p=p.next;
            length++;
        }
        if(k>length)return null;
        for(int i=0;i<length-k;i++)pListHead=pListHead.next;
        return pListHead;
    }
}

Python 代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def findKthToTail(self, pListHead, k):
        """
        :type pListHead: ListNode
        :type k: int
        :rtype: ListNode
        """
        length=0
        p=pListHead
        while p!=None:
            p=p.next
            length+=1
        if k>length:
            return None
        for i in range(length-k):
            pListHead=pListHead.next
        return pListHead

Javascript 代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} pListHead
 * @param {number} k
 * @return {ListNode}
 */
var findKthToTail = function(pListHead, k) {
    var length=0;
    var p=pListHead;
    while(p!=null){
        p=p.next;
        length++;
    }
    if(k>length)return null;
    for(var i=0;i<length-k;i++)pListHead=pListHead.next;
    return pListHead;
};

Python3 代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def findKthToTail(self, pListHead, k):
        """
        :type pListHead: ListNode
        :type k: int
        :rtype: ListNode
        """
        length=0
        p=pListHead
        while p!=None:
            p=p.next
            length+=1
        if k>length:
            return None
        for i in range(length-k):
            pListHead=pListHead.next
        return pListHead

Go 代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func findKthToTail(pListHead *ListNode, k int) *ListNode {
    length:=0
    p:=pListHead
    for p!=nil{
        p=p.Next
        length++
    }
    if k>length{
        return nil
    }
    for i:=0;i<length-k;i++{
        pListHead=pListHead.Next
    }
    return pListHead
}