Java题：查找单链表中第 k 个节点元素的值

遇到过一道奇奇怪怪的Java题，就整理出自己的想法，不知道对不对，还望大佬们指导。

题目

给定一个单链表，查找单链表中第 k 个节点元素的值，同时要求使用时间复杂度低的算法实现。

单链表的定义如下：

class ListNode {

    int val;

    ListNode next;

    ListNode(int val){

        this.val=val;

    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13

我的想法

这题很迷惑，我的两种思考方向是：

1. Java书上说：遍历链表，使用迭代器要比get()快

2. 单纯考虑时间复杂度都是O(n)。但是快慢指针（跳表） 会不会更好一点呢？我不确定

总之就是非常迷惑。

我的代码

快慢指针、指针、迭代器 三种写法

import java.util.Iterator;

class ListNode {
	int val;
	ListNode next;

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

public class List {
	
//	快慢指针
	public static int findKthNode(ListNode head, int k) {
	    ListNode fast = head;
	    for (int i = 0; i < k - 1; i++) {
	        fast = fast.next;
	        if (fast == null) {
	            return -1; // 返回 -1 表示 链表长度小于k
	        }
	    }
	    ListNode slow = head;
	    while (fast.next != null) {
	        fast = fast.next;
	        slow = slow.next;
	    }
	    return slow.val;
	}
	
//	指针
	public static int findKthNode1(ListNode head, int k) {
	    ListNode current = head;
	    int count = 1; // 记录迭代的次数，从1开始

	    while (current != null && count < k) {
	        current = current.next;
	        count++;
	    }

	    if (current == null) {
	        return -1; // 返回 -1 表示 链表长度小于k
	    }

	    return current.val;
	}

//	迭代器
	public static int findKthNode2(ListNode head, int k) {
		Iterator iterator = new Iterator(){
	        ListNode current = head;
	        public boolean hasNext() {
	            return current != null;
	        }

	        public ListNode next() {
	            ListNode node = current;
	            current = current.next;
	            return node;
	        }

	        public void remove() {
	            throw new UnsupportedOperationException("Unsupported operation: remove");
	        }
	    };
	    
		ListNode target = null;
	    int count = 0;
	    while (iterator.hasNext()) {
	        ListNode node = iterator.next();
	        count++;
	        if (count == k) {
	            target = node;
	            break;
	        }
	    }

	    if (target == null) {
	    	return -1; // 返回 -1 表示 链表长度小于k
	    }

	    return target.val;
	}
	
    public static void main(String[] args) {
    	// 创建一个示例链表：1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        // 创建一个实例对象
        Main main = new Main();

        // 测试查找第 k 个节点元素的值
        int k = 3;
        int result1 = findKthNode(head, k); // 快慢指针
        int result2 = findKthNode1(head, k); // 指针
        int result3 = findKthNode2(head, k); // 迭代器
        System.out.println("快慢指针实现 ：第 " + k + " 个节点的值为：" + result1);
        System.out.println("指针实现 ：第 " + k + " 个节点的值为：" + result1);
        System.out.println("迭代器实现 ：第 " + k + " 个节点的值为：" + result1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

输出

快慢指针实现 ：第 3 个节点的值为：3
指针实现 ：第 3 个节点的值为：3
迭代器实现 ：第 3 个节点的值为：3
1
2
3

还是不太懂题目的真正含义，还望大佬指点