[剑指offer][Java]链表中倒数第k个结点

题目

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

程序核心思想

• 思路一：求得链表的总长度，然后用总长度-k+1，就得到了正数的位置，就可以返回它了。
• 思路二：快慢指针。快指针先走k-1步，然后一起走，快指针走到结尾时，慢指针就走到倒数第k个结点了。

Tips

• 这个题目有一个比较隐蔽（可能我比较傻）的边界条件：要返回第k个结点，但是链表根本就没有这么长。
• 第二个就是要检查它给的数据的合理性，比如如果链表为空（这个比较好想），那么返回肯定是Null；如果它让返回倒数第0个或者倒数-1个结点，应该就属于不合理的数据了（倒数-1个是不是可以理解为正数第一个？？？不太清楚。。），可以在最开始就给他排除出去。

代码

思路一：

/*
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;
        
        int number = 1;
        ListNode pointer = head;
        while(pointer.next != null){
            pointer = pointer.next;
            number++;
        }
        
        if(k > number){
            return null;
        }
        
        int location = number - k + 1;
        pointer = head;
        while(location > 1){
            pointer = pointer.next;
            location--;
        }
        
        return pointer;
    }
}

思路二：

/*
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;
        
        ListNode fast = head;
        ListNode slow = head;
        
        while(k > 1){
            if(fast.next != null){
                fast = fast.next;
                k--;
            }else{
                return null;
            }
        }
        
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        
        return slow; 
    }
}