查找链表倒数第N个元素

查找链表倒数第N个元素:
链表应用很广泛,有单向链表,双向链表。单向链表如何查找倒数第n个元素呢?本文以java代码实现链表反向查找。

单向链表的定义

单向链表,主要有数据存储,下一个节点的引用这两个元素组成。

1
2
3
4
5
6
7
8
public class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}

遍历倒数第n个元素

在查找过程中,设置两个指针,让其中一个指针比另一个指针先前移k-1步,
然后两个指针同时往前移动。循环直到先行的指针指为NULL时,另一个指针所指的位置就是所要找的位置
算法复杂度为o(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public Node findDescEle(Node head, int k) {
if (k < 1 || head == null) {
return null;
}
Node p1 = head;
Node p2 = head;
//前移k-1步
int step = 0;
for (int i = 0; i < k; i++) {
step++;
if (p1.next != null) {
p1 = p1.next;
} else {
return null;
}
}
while (p1 != null) {
step++;
p1 = p1.next;
p2 = p2.next;
}
System.out.println("o(n)==" + step);
return p2;
}

总结

查找链表倒数第n个元素,复杂度为o(n),使用两个指针即可简单实现。

博客搬家,请访问新博客地址吧! 我的博客

文章目录
  1. 1. 单向链表的定义
  2. 2. 遍历倒数第n个元素
  3. 3. 总结
,