倒数第k个节点
求单链表倒数第k个节点思路:
定义p1p2两个节点
然后p2指向正想第k个
接着 p1 p2同时后移(间距为k)直到p2==null
则此时p1就是倒数第k个节点
如果返回 null 对象则无法get node.value 这个值
代码
package _09_Linear;
public class BottomKthNode {
static class Node {
Object value;
Node next;
public Node(Object value) {
this.value = value;
}
@Override
public String toString() {
return "" + value;
}
}
public Node FindKthToTail(Node head, int k) {
if (head == null || k <= 0) {
return head;//如果返回 null 对象则无法get node.value 这个值
}
Node p1 = head;
Node p2 = head;
int count = 0;
while (p2 != null && count < k) {
p2 = p2.next;
count++;
}
if (count < k) {
return head;//如果返回 null 对象则无法get node.value 这个值
}
while (p2 != null) {
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
public static void main(String[] args) {
int arr[] = {9, 8, 7, 2, 8, 4, 2, 4, 2};
Node head = new Node(null);//头指针一定为空
Node p = head;
for (int i = 0; i < arr.length; i++) {
p.next = new Node(arr[i]);
p = p.next;
}
//Test
Node ans = new BottomKthNode().FindKthToTail(head, 9);
System.out.println(ans.toString());
ans = new BottomKthNode().FindKthToTail(head, 1);
System.out.println(ans.toString());
ans = new BottomKthNode().FindKthToTail(head, 7);
System.out.println(ans.toString());
}
}
本文作者:Author: 寒光博客
文章标题:[java] 链表实战 倒数第k个节点
本文地址:https://dxoca.cn/java/292.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/292.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。