链表中倒数第k个结点

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

两个指针来实现，首先确保第一个指针领先第二个k个位置。其次两个指针同步走，一直走到底，第二指针所示位置自然为倒数第k个。

  
package main

import (
    "fmt"
)

type NodeList struct {
    Val  int
    Next *NodeList
}

func kthNode(head *NodeList, k int) *NodeList {
    if head == nil {
        return head
    }
    tail := head
    for k > 1 && tail != nil {
        tail = tail.Next
        k--
    }
    if tail == nil {
        return nil
    }
    for tail.Next != nil {
        tail = tail.Next
        head = head.Next
    }
    return head
}

class ListNode:
    def __init__(self, x):
        self.val = x
        self.Next = None

class Solution:
    def FindKthTail(self, head, k):
        if head == None or k <= 0:
            return None

        pHead = head
        pBehind = None

        for i in range(k-1):
            if pHead.Next != None:
                pHead = pHead.Next
            else:
                return None

        pBehind = head
        while pHead.Next != None:
            pHead = pHead.Next
            pBehind = pBehind.Next
        return pBehind