【链表2】链表中倒数第k个结点

：

题目描述

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

有很多种方法，要么用集合，要么用双指针的方法。

方法一：集合(这里的每次移除的数要特别注意)

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.ArrayList;

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k<=0)
            return null;
        ArrayList<ListNode> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        int size=list.size();
        //判断，如果倒数第k个数大于链表长度
        if(k > size)
            return null;
        int count =0 ;
        //倒数第k个数，即从尾部移除k-1个数后的那个数即为第k个数
        while(count != k-1){
            //每次移除集合尾部最后一个数，注意是size-1
            list.remove(--size);
            count ++;
        }
        
        return list.remove(--size);
        
    }
}

方法二：双指针法

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        //1 判断 k<=0 或k>链表长度，都为错误输入
        if(head == null || k<=0)
            return null; 
        int len =0; 
        ListNode tempNode = head;
        while(tempNode!=null){
            len++;
            tempNode = tempNode.next;
        }
        if(k>len)
            return null;
        
        //2  设置双指针
        ListNode firstIndexNode = head;
        ListNode secondIndexNode = null;
        //让第一个指针先走k-1步
        for(int i=0;i<k-1;i++){
            if(firstIndexNode != null){
                 firstIndexNode = firstIndexNode.next;
            }else{
                return null;
            }
        }
       secondIndexNode=head;
        
        //第一个指针走到尾部，第二个指针刚好指向第k个结点
       while(firstIndexNode.next!= null){
           firstIndexNode = firstIndexNode.next;
           secondIndexNode = secondIndexNode.next;
       }
       
        return secondIndexNode;
    }
}