Чтобы понять эту проблему, мы должны сделать простую аналогию с примером измерения. Допустим, вы должны найти место вашей руки, которое находится на расстоянии 1 метра от среднего пальца, как бы вы измерили? Вы бы просто схватили линейку длиной 1 метр и приложили верхний конец этой линейки к кончику среднего пальца, а нижний конец метра будет точно на расстоянии 1 метра от верха вашего среднего пальца. палец.
То, что мы делаем в этом примере, будет таким же, нам просто нужен кадр с шириной n-элемент, и нам нужно поместить кадр в конец списка, таким образом, начальный узел кадра будет ровно n-й элемент до конца списка.
Это наш список, предполагая, что в списке M элементов, а наш фрейм с шириной N элементов;
HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)
<-- Frame -->
Однако нам нужны только границы кадра, поэтому конечная граница кадра будет точно (N-1) элементов удалена от начальной границы кадра. Так что нужно хранить только эти граничные элементы. Давайте назовем их A и B;
HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)
A <- N-Element Wide-> B
Первое, что мы должны сделать, это найти B, который является концом кадра.
ListNode<T> b = head;
int count = 1;
while(count < n && b != null) {
b = b.next;
count++;
}
Теперь b - это n-й элемент массива, а a находится на HEAD . Таким образом, наш фрейм установлен, и мы будем постепенно увеличивать оба граничных узла, пока b не достигнет конца списка, где a будет n-ным к последний элемент;
ListNode<T> a = head;
while(b.next != null) {
a = a.next;
b = b.next;
}
return a;
Чтобы собрать все, и с проверками HEAD, N
public ListNode<T> findNthToLast(int n) {
if(head == null) {
return null;
} else {
ListNode<T> b = head;
int count = 1;
while(count < n && b != null) {
b = b.next;
count++;
}
if(count == n && b!=null) {
ListNode<T> a = head;
while(b.next != null) {
a = a.next;
b = b.next;
}
return a;
} else {
System.out.print("N(" + n + ") must be equal or smaller then the size of the list");
return null;
}
}
}