链表中倒数第k个结点

题目来源：牛客网--链表中倒数第k个结点

题目描述

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

解题思路

整体思路就是两步走，两人刚开始都是1，
第一个人走到K+1时，第二个人也开始走，两个人速度一样。
当第一个人走完时，第二个人刚好比第一个人慢了 K

提交代码

// 整体思路就是两步走，两人刚开始都是1，
// 第一个人走到K+1时，第二个人也开始走，两个人速度一样。
static ListNode method(ListNode head, int k) {
    // 非法输入
    if (k <= 0 || head == null) {
        return null;
    }

    ListNode result = head;
    ListNode current = head;
    int i = 1;
    for (; current != null; i++) {
        // 如果current已经走到了第 K+1 个，result开始往后移
        // 因为 result 本来就指向第 1 个
        if (i > k) {
            result = result.next;
        }
        // 链表向后移动
        current = current.next;
    }
    return i > k ? result : null;
}

本地测试代码

public class FindKthToTail {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode current = head;
        // 生成长度为5的链表
        for (int i = 2; i <= 5; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }
        System.out.println(method(head,0).val);
    }
    
    // 整体思路就是两步走，两人刚开始都是1，第一个人走到K+1时，第二个人也开始走，两个人速度一样。
    static ListNode method(ListNode head, int k) {
        // 非法输入
        if (k <= 0 || head == null) {
            return null;
        }

        ListNode result = head;
        ListNode current = head;
        int i = 1;
        for (; current != null; i++) {
            // 如果current已经走到了第 K+1 个，result开始往后移
            // 因为 result 本来就指向第 1 个
            if (i > k) {
                result = result.next;
            }
            // 链表向后移动
            current = current.next;
        }
        return i > k ? result : null;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}