当前位置：首页 > news >正文

链表中倒数第K个节点 -- java

news 来源：原创 2024/5/14 6:16:32

题目描述

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

节点定义如下：

public class ListNode {
    int value;
    ListNode next = null;

    public ListNode() {
    }

    public ListNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "value=" + value +
                '}';
    }
}

测试用例

功能测试（第k个节点在链表的中间；第k个节点是链表的头结点；第k个节点是链表的尾结点）
特殊输入测试（链表头结点为空指针；链表的节点总数少于k；k=0）

解题思路

定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1步，当第一个指针到达链表的尾节点时，第二个指针正好指向倒数第k个节点。

k-1可以这么理解：倒数第一个节点和尾结点的距离是0，倒数第二个节点和尾结点的距离是1，所以倒数第k个节点和尾结点的距离是k-1。

但是为了保持程序的鲁棒性，需要考虑下面三个问题：

输入头节点为空指针
链表的节点总数少于k
输入k为0

代码

public class FindKthToTail {
    public static ListNode findKthToTail(ListNode head, int k) {
        // 防止空指针和k=0无意义
        if (head == null || k == 0) {
            return null;
        }

        // 第一个指针的步数
        int i = 0;
        // 初始化两个指针
        ListNode firstNode = head;
        ListNode secondNode = head;

        while (firstNode.next != null) {
            firstNode = firstNode.next;
            i++;
            // 保持两个指针距离为k-1
            if (i > k-1) {
                secondNode = secondNode.next;
            }
        }

        // 还没走到k-1步就结束了
        // 表示链表的节点总数少于k
        if (i < k-1) {
            return null;
        }

        return secondNode;
    }

    // 测试
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;


        System.out.println(findKthToTail(node1, 1)); // 倒数第1个节点
        System.out.println(findKthToTail(node1, 3)); // 倒数第3个节点
        System.out.println(findKthToTail(node1, 5)); // 倒数第5个节点


        System.out.println(findKthToTail(null, 1)); // 头结点为null
        System.out.println(findKthToTail(node1, 6)); // 节点总数小于k
        System.out.println(findKthToTail(node1, 0)); // k等于=
    }
}