前言

在算法练习中，查找单链表中的倒数第 K 个节点是一个经典的题目。今天我们将探讨如何用 Java 编写一个算法，来高效地找到单链表中的倒数第 K 个节点。

---

问题描述 :

给定一个单链表，编写一个函数，查找链表中的倒数第 K 个节点。如果该节点不存在，则返回 null。

例如，给定链表：1 -> 2 -> 3 -> 4 -> 5，如果 K = 2，返回节点 4。

解决思路

解决这个问题的常见方法是 双指针 技巧。通过使用两个指针，我们可以在一次遍历中找出倒数第 K 个节点。具体步骤如下：

1.设置两个指针：

• 第一个指针从链表的头部开始，向前走 K 步。此时，第二个指针仍然指向链表的头部。

2.同步移动两个指针：

• 让两个指针同时向后移动，每次同时走一步。当第一个指针走到链表的末尾时，第二个指针恰好指向倒数第 K 个节点。

3.返回第二个指针的值：

• 当第一个指针到达链表末尾时，第二个指针所指向的节点就是倒数第 K 个节点。

这种方法只需要遍历链表一次，时间复杂度为 O(n)，空间复杂度为 O(1)。

Java 代码实现

我们先定义一个链表节点的类 ListNode，然后实现查找倒数第 K 个节点的函数。

1. 定义单链表节点类 ListNode

public class ListNode {
    int val;
    ListNode next;

    // 构造函数
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

2. 查找倒数第 K 个节点的函数

public class LinkedList {
    // 查找倒数第 K 个节点
    public static ListNode findKthFromEnd(ListNode head, int k) {
        // 如果链表为空或k小于等于0，直接返回null
        if (head == null || k <= 0) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        // 让 fast 指针先走 K 步
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                return null; // 如果链表长度小于 K，返回 null
            }
            fast = fast.next;
        }

        // 同步移动 fast 和 slow 指针，直到 fast 到达链表的末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 此时 slow 指向的就是倒数第 K 个节点
        return slow;
    }

    // 打印链表的辅助函数
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // 创建一个测试链表 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.println("链表内容：");
        printList(head);

        int k = 2;
        ListNode result = findKthFromEnd(head, k);

        if (result != null) {
            System.out.println("倒数第 " + k + " 个节点是: " + result.val);
        } else {
            System.out.println("链表长度小于 " + k);
        }
    }
}

代码解析

1.findKthFromEnd 方法：

• 使用两个指针 fast 和 slow。首先让 fast 指针走 K 步。如果链表长度小于 K，直接返回 null。
• 然后同时移动两个指针，直到 fast 到达链表的末尾。此时，slow 指针指向的就是倒数第 K 个节点。

2.printList 方法：

• 用于打印链表，帮助我们查看链表的结构。

3.main 方法：

• 创建一个链表 1 -> 2 -> 3 -> 4 -> 5，然后调用 findKthFromEnd 方法查找倒数第 K 个节点。

时间与空间复杂度分析

• 时间复杂度：O(n)，我们只遍历了链表一次，其中 n 是链表的长度。
• 空间复杂度：O(1)，只使用了常量空间来存储两个指针 fast 和 slow，没有使用额外的数据结构。

---

总结

通过双指针技巧，我们能够高效地查找单链表中的倒数第 K 个节点。这个方法具有 O(n) 的时间复杂度和 O(1) 的空间复杂度，非常适合用于大规模数据的处理。如果你在实际开发中遇到类似的问题，这种技巧将会非常有用。

如果此篇文章有帮助到您, 希望打大佬们能关注、点赞、收藏、评论支持一波，非常感谢大家！
如果有不对的地方请指正!!!
参考1