每天一道剑指offer-链表中倒数第k个结点

乔戈里

发布于 2019-09-17 16:15:42

2700

发布于 2019-09-17 16:15:42

文章被收录于专栏：Java那些事

今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

昨天的题解

题目

每天一道剑指offer-链表中倒数第k个结点来源：牛客网对应专题

题目详述

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

题目详解

思路

就是快慢指针，快指针先走k-1步，然后快慢指针一起走，当快指针走到末尾，那么慢指针就到了倒数第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) {
        int length = 0;
        ListNode tempHead = head;
        while(tempHead != null)
        {
            length++;//这里计算链表的长度
            tempHead = tempHead.next;
        }
        if(k > length || k <=0)//因为倒数第K个节点，如果超过链表长度可不行呀
            return null;
        ListNode before = head;
        ListNode after = head;
        for(int i=0;i<k-1;i++)快指针先走k-1步
            before = before.next;
        while(before.next != null)
        {
            before = before.next;
            after = after.next;//快慢指针一起走。
        }
        return after;
    }
}