题解 | #链表中倒数最后k个结点#

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
    // 特判
    if k == 0 {
        return nil
    }
    
    // 倒数第 2 个节点，就是逆序后的第 2 个节点
    pHead = reverse(pHead)
    
    cur := pHead
    for k > 1 && cur != nil {
        cur = cur.Next
        k--
    }

    reverse(pHead)

    return cur
}

func reverse(root *ListNode) *ListNode {
    if root == nil {
        return nil
    }

    var pre *ListNode

    for root != nil {
        next := root.Next

        root.Next = pre
        pre = root
        root = next
    }

    return pre
}

1. 倒数第 k 个对应逆置链表的正数第 k 个节点的指针（因为逆置后的 root 已经指向第一个节点，那么 k 的控制范围应该是 k > 1，将第一个节点的计数要减去）； 2. 再次逆置链表，将倒数第 k 个的指针返回即可。

• 整个过程的指针变化情况：

可以看到无论我们怎么逆置，每个节点的地址是不变的，修改的只是 Next 的指向，因此只要我们求出逆置后第 K 个节点的地址就相当于得到了倒数第 K 个节点的地址，最后我们将链表还原成原来的形式就可以了。