本文共 1883 字，大约阅读时间需要 6 分钟。

一、问题描述

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

二、代码实现

采用双指针法，首先，快指针先走k步，慢指针先走一步；然后，快慢指针同时移动，当快指针走到链表末尾节点的时候，慢指针就刚好走到倒数第k个节点。

这道题不合格的边界条件有：head == null、k <= 0，此外不合法的情况还有链表的长度小于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 || k == 0) {            return null;        }                //1、快指针先走k步，慢指针先走1步        ListNode slow = head, fast = head;        while (fast != null && k > 1) {            fast = fast.next;            k --;        }        //排除单链表长度小于k的情况        if (fast == null) {            return null;        }                //2、快慢指针一起走，当快指针到达最后一个节点时，慢指针就是倒数第k个节点        while (fast.next != null) {            slow = slow.next;            fast = fast.next;        }        return slow;    }        public ListNode FindKthToTail2(ListNode head, int k) {        if (head == null)            return null;                ListNode P1 = head;        while (P1 != null && k-- > 0)            P1 = P1.next;        if (k > 0)            return null;        ListNode P2 = head;        while (P1 != null) {            P1 = P1.next;            P2 = P2.next;        }        return P2;    }            public ListNode FindKthToTail(ListNode head,int k) {              int size = 0;        ListNode cur = head;        while (cur != null) {            size++;            cur = cur.next;        }        if (size < k || k == 0) {            return null;        }                        //int diff = size - k;        ListNode pre = head, post = head;        int count = 0;        while (count < k-1) {            post = post.next;            count++;        }                while (post.next != null) {            post = post.next;            pre = pre.next;        }                return pre;    }}

转载地址：http://nfnii.baihongyu.com/