链表中倒数第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) {

    }
}

解题一-直接输出结点的值

1.思路
由题中可以推断出：倒数第K个结点是正数第n-k+1个结点（n表示链表长度）。
如链表为1->2->3->4->5 当输出倒数第4个结点（即元素为2）时，正数（元素为2）为第5-4+1个结点。
[可行但不高效的常规解法:这种思路需要遍历链表两次，第一次统计出链表中结点的个数，第二次才能找到倒数第k个结点。]
2.代码如下

/*
public class ListNode {
    int val;//存放数据的变量
    ListNode next = null;//存放结点的变量，默认为null

    ListNode(int val) {   //构造方法
        this.val = val;
    }
}*/
public class Solution{
    public ListNode FindKthToTail(ListNode head,int k) {
       //定义链表的长度
        int totalNum=0;
        //判断head是否为空，为空则返回
        if(head!=null){
            totalNum++;
        }else{
            return null;
        }
        //计算总的结点数量
        ListNode currentNode=head.next;
        while(currentNode!=null){
            totalNum++;
            currentNode=currentNode.next;
        }
        if(totalNum < k){
            //throw new RuntimeException("k的值超过了链表长度");
            return null;
        }
        //倒数第k个为正数第totalNum-k+1个
        ListNode resultNode = head;
        for(int i=1;i<=totalNum-k;i++){
            resultNode = resultNode.next;
        }
        return resultNode; 
    }
}

解题二-定义两个指针

1.思路
为了能够只遍历一次就能找到倒数第k个节点，可以定义两个指针：
（1）第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；
（2）从第k步开始，第二个指针也开始从链表的头指针开始遍历；
（3）由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
下图展示了在有6个结点的链表上找倒数第3个结点的过程：

image.png

举一反三：当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。

2.代码

/*
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 pre=head;
        ListNode last=head;
        //先将一个节点往后移动k-1个距离
        for(int i=1;i<k;i++)
        {
            if(pre.next!=null)
            {
                pre=pre.next;
            }else
            {
                return null;
            }
        }
        //一起移动
        while(pre.next!=null)
        {
            pre=pre.next;
            last=last.next;
        }
        return last;
    }
}