Java解算法题：找出单向链表中的第k个节点关键词：双指针

怼烎@ 2024-03-24 13:48 33阅读 0赞

**题目：**

> ### 描述 ###
> 
> 输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
> 
> 链表结点定义如下：
> 
>     struct ListNode
>     {
>         int m_nKey;
>         ListNode* m_pNext;
>     };
> 
> 正常返回倒数第k个结点指针，异常返回空指针.
> 
> **要求：**
> 
> **(1)正序构建链表;**
> 
> **(2)构建后要忘记链表长度。**
> 
> 数据范围：链表长度满足 1≤n≤1000 ， k≤n ，链表中数据满足 0≤val≤10000
> 
> 本题有多组样例输入。
> 
> #### 输入描述： ####
> 
> 输入说明  
> 1 输入链表结点个数  
> 2 输入链表的值  
> 3 输入k的值
> 
> #### 输出描述： ####
> 
> 输出一个整数
> 
> ### 示例1 ###
> 
> 输入：
> 
>     8
>     1 2 3 4 5 6 7 8
>     4
> 
> 输出：
> 
>     5

本题使用双指针来解，具体思路是这样的：

![c67586ec43a64208bad679f0122713dc.png][]

简而言之，双指针就是 fast 先动，slow 后动，代码如下：

import java.util.Scanner;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) { // 注意 while 处理多个 case
                int a = in.nextInt();
                // 初始化链表头结点head
                ListNode head = new ListNode(in.nextInt(), null);
                // cur用来操作当前节点，与下一节点建立链接
                ListNode cur = head;
                for (int i = 0; i < a - 1; i++) {
                    ListNode node = new ListNode(in.nextInt(), null);
                    cur.next = node;
                    cur = cur.next;
                }
                int k = in.nextInt();//倒数第k个节点
                ListNode fast = head;//快指针
                int i = 1;
                while (i < k) {//fast先动
                    fast = fast.next;
                    i++;
                }
                ListNode slow = head;
                while (fast.next != null) {
                    fast = fast.next;
                    slow = slow.next;//slow后动
                }
                System.out.println(slow.key);//结束移动后，直接输出slow节点的值
            }
        }
        static class ListNode{
            int key;
            ListNode next;
            public ListNode(int k, ListNode next) {
                this.key = k;
                this.next = next;
            }
        }
    }

[c67586ec43a64208bad679f0122713dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/398367a10bcf47a99efb2498a4e2ff44.png