2019独角兽企业重金招聘Python工程师标准>>>
问题描述:
输入一个单向链表,输出该链表中倒数第k个结点。链表倒数第0个节点为NULL。
public static class Node{
public int data;
public Node next = null;
public Node(int d, Node p){
data = d;
next = p;
}
}
分析:
方法1:
递归
private int nthToLastv1(Node p, int k){
if(p.next == null)
return 0;
int i = nthToLastv1(p.next, k) + 1;
if(k == i)
System.out.println(p.data);
return i;
}
方法2:
非递归
private void nthToLastv2(int k){
Node p1 = head.next;
Node p2 = head.next;
for (int i = 1; i < k; i++){
p2 = p2.next;
}
while(p2.next != tail){
p1 = p1.next;
p2 = p2.next;
}
if(p1 != null) System.out.println(p1.data);
}