链表中倒数第k个节点

题目描述

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

解题思路

• 由题所知，设链表长度为 N，需要得到链表中倒数第 k 个结点，正数则为第 (N-k)+1) 个结点。知道N-k则解决问题。
• 则可以设定两个指针 A、B，由A先移动k个结点，则还剩N-k个结点，此时让 A 和 B 同时移动，可以知道当 A 移动到链表结尾时，B 移动到 N - k 个节点处，该位置就是倒数第 k 个节点。

代码

/*
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){
            return null;
        }
        ListNode A = head;
        while(A != null && k > 0){
            k--;
            A = A.next;
        }
        if(k > 0){
            return null;
        }
        ListNode B = head;
        while(A != null){
            A = A.next;
            B = B.next;
        }
        return B;
    }
}