JZ22-链表中倒数第k个结点-牛客网题解

描述

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

示例1

输入：1,{1,2,3,4,5}

返回值：{5}

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k<=0 || head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while((--k)>0){
            fast=fast.next;
            if(fast==null){
                return null;
            } 
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

解题思路：利用快慢指针。使快指针比慢指针快k个结点。之后一块右移，直到快节点移到链表尾

public ListNode FindKthToTail1(ListNode head,int k) {//16ms 9836KB
        if(head==null || k<=0) return null;
        int n=0;
        ListNode cur=head;
        while(cur!=null){
            cur=cur.next;
            n++;
        }
        if(n<k) return null;
        n-=k;
        while(n>0){
            head=head.next;
            n--;
        }
        return head;
    }

解题思路：先遍历出链表长度，计算n-k，再进行二次遍历。

注意异常跳出情况:k<0或者k>数组的长度或者数组为空，需要返回空。