链表中倒数第k个节点https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9

1. 思路

从题目中给出的有效信息：
返回倒数第k个节点，前提是存在至少k个节点

2. 解法

2.1 解法1： 暴力求解法

代码如下：

package main
import . "nc_tools"
/*
 * 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
    // 获取原链表的总长度
    length := getLength(pHead)
    // 不存在至少k个节点，则返回空
    if length < k {
        return nil
    }
    //计算倒数第k个节点的位置，即从头节点起，移动(总长度-k)次
    toReturn := length - k
    for i := 0; i < toReturn; i++ {
        pHead = pHead.Next
    }
    //将倒数最后k个节点返回
    return pHead
}
// 计算原链表总长度的函数
func getLength (pHead *ListNode) int {
    res := 0
    for pHead != nil {
        res++
        pHead = pHead.Next
    }
    return res
}

复杂度分析：

1. 时间复杂度：O(n)，其中n为链表的长度，在链表上遍历两次
2. 空间复杂度：O(1)，只需要开辟常数大小的新空间

2.2 解法2： 双指针法

代码如下：

package main
import . "nc_tools"
/*
 * 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
    // p和q为两个链表节点指针，p在前而q在后，之间距离为k，故p到链表末尾时，q恰为倒数第k个节点，可供返回
    p, q := pHead, pHead
    var i int
    for ; p != nil; i++ {
                // 首先移动p指针，待其移动k次后，方可移动q指针
        if i >= k {
            q = q.Next;
        }
        p = p.Next;
    }
    // 此时i即为链表总长度，如不存在k个节点，则返回空
    if i < k {
        return nil
    }
    return q
}

复杂度分析：

1. 时间复杂度：O(n)，其中n为链表的长度，在链表上仅需一次遍历
2. 空间复杂度：O(1)，只需要开辟常数大小的新空间