一方向チェーンテーブルの最後からk番目のノードを見つけるアルゴリズム
2274 ワード
再帰と非再帰の2つの方法があります
アルゴリズム1(非再帰方式):最も簡単な方法は最初から遍歴することである.
アルゴリズム2(再帰方式)は、k番目の要素の値を印刷する.
アルゴリズム3(反復法):より効率的だが、あまり直感的ではない解法.
アルゴリズム1(非再帰方式):最も簡単な方法は最初から遍歴することである.
アルゴリズム2(再帰方式)は、k番目の要素の値を印刷する.
public static int nthToLast(LinkedListNode head,int k){
if(head == null){
return 0;
}
int i=nthToLast(head.next,k)+1;
if(i==k){
System.out.println(head.data);
}
return i;
}
アルゴリズム3(反復法):より効率的だが、あまり直感的ではない解法.
LinkedListNode nthToLast2(LinkedListNode head, int k) {
if (k <= 0) {
return null;
}
LinkedListNode p1 = head;
LinkedListNode p2 = head;
//p2 k
for(int i=0;i<k-1;i++){
if(p2.next==null){
return null;
}
p2 = p2.next;
}
if(p2==null){
return null;
}
/* p1 p2, p2 */
/*p1 k */
while(p2.next!=null){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}