Поиск "Nth node с конца" связанного списка
Кажется, это вернет правильный ответ, но я не уверен, действительно ли это лучший способ заниматься вещами. Похоже, что я посещаю первые n узлов слишком много раз. Какие-либо предложения? Обратите внимание, что я должен сделать это с помощью отдельного списка.
Node *findNodeFromLast( Node *head, int n )
{
Node *currentNode;
Node *behindCurrent;
currentNode = head;
for( int i = 0; i < n; i++ ) {
if( currentNode->next ) {
currentNode = currentNode->next;
} else {
return NULL;
}
}
behindCurrent = head;
while( currentNode->next ) {
currentNode = currentNode->next;
behindCurrent = behindCurrent->next;
}
return behindCurrent;
}
Ответы
Ответ 1
Другой способ сделать это без посещения узлов дважды:
Создайте пустой массив размера n, указатель на этот массив, начинающийся с индекса 0, и начните итерацию с начала связанного списка. Каждый раз, когда вы посещаете node, храните его в текущем индексе массива и продвигайте указатель на массив. Когда вы заполняете массив, оберните и перезапишите ранее сохраненные элементы. Когда вы дойдете до конца списка, указатель будет указывать на элемент n из конца списка.
Но это также просто алгоритм O (n). То, что вы сейчас делаете, прекрасно. Я не вижу веских причин для его изменения.
Ответ 2
Начните два указателя. Перенесите первый элемент N
вперед, а затем переместите каждый указатель 1. Когда первый указатель достигнет конца, второй указатель даст ответ.
EDIT. Да, это почти тот же код, что и в вопросе. Но я чувствую, что псевдокод делает его более ясным. Чтобы ответить на вопрос, нет другого выхода, поскольку первые N
элементы должны посещаться дважды. Если N
мало, это не имеет значения. Если N
велико, то второй цикл будет небольшим. Таким образом, это всегда решение O(n)
.
Ответ 3
Поддерживайте 2 указателя на узлах. Когда первый указатель достигает хвоста, второй указатель будет указывать на желаемый node.
код:
typedef struct _node //define the list node
{
int i;
struct _node *next;
} Node;
Node * findNode(Node *listHead, int n)
{
Node *ptr1, *ptr2; // we need 2 pointers
ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially
while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
{
if(n > 0)
{
ptr1 = ptr1->next; //increment only the 1st pointer
n--;
}
else
{
ptr1 = ptr1->next; //increment both pointers
ptr2 = ptr2->next;
}
}
return ptr2; //now return the ptr2 which points to the nth node from the tail
}
Ответ 4
Я использую статическую переменную 'i', которая будет увеличиваться
в то время как возвращение с конца списка. Как и в
мы будем в основном отслеживать Nth
элемент, начинающийся с конца связанного списка.
Рекурсия помогает нам отслеживать с конца.
static int i;
public static void NthToLast(LinkedListNode head, int n)
{
if (head == null)
return;
NthToLast(head.Next, n);
i++;
if (n == i)
{
Console.WriteLine("Mth to last" + head.Data);
return;
}
}
Ответ 5
Используйте два указателя pTemp и NthNode. Изначально обе точки указывают на node списка. NthNode начинает движение только после того, как pTemp выполнил n ходов. От обоих движений вперед, пока pTemp не достигнет конца списка. В результате NthNode указывает на nth node с конца связанного списка.
public ListNode NthNodeFromEnd(int n){
ListNode pTemp = head, NthNode = null;
for(int count=1; count<n;count++){
if(pTemp!=null){
pTemp = pTemp.getNext();
}
}
while(pTemp!=null){
if(NthNode==null){
NthNode = head;
}
else{
NthNode = NthNode.getNext();
}
pTemp = pTemp.getNext();
}
if(NthNode!=null){
NthNode = NthNode.getNext();
return NthNode;
}
return null;
}
Refer TextBook: "Структура данных и алгоритмы упрощены на Java"
Ответ 6
Ваше время работы по-прежнему равно O (n), поэтому я не вижу проблемы с ним.
Концептуально вы можете разделить список на две части: часть до node, которую вы возвращаете, и часть после. Одну из этих частей придется пройти дважды. Ваша реализация выбрала первое, в преимуществе без использования дополнительной памяти (кроме пары временных переменных).
В качестве альтернативы вы можете создать стек, пройти список и поместить каждый элемент в стек, а затем удалить n элементов. Тогда вы будете идти в конце списка дважды, а не в начале. Это имеет недостаток в сохранении списка в памяти дважды. (Вы могли бы сделать стек немного умнее, только сохраняя n элементов и отбрасывая их со дна стека, когда новые добавляются, тогда вы используете достаточно места для хранения n узлов.)
Я предполагаю, что вы не можете сдуть список, обратив его на место. Затем она постоянная память, еще O (n), все еще идущая в конце списка дважды.
Ответ 7
Node* fetchNNodeFrmLast(int arg)
{
Node *temp = head;
Node *nNode = head;
if(head == NULL || arg <= 0)
{
Printf("Either head is null or invalid number entered");
return;
}
while(temp != NULL)
{
temp = temp->next;
if(arg > 1)
{
arg--;
continue;
}
nNode = nNode->next;
}
return nNode;
}
Ответ 8
Вы можете использовать двусвязный список, который является связанным списком, который также сохраняет адрес этого родителя. Трансверсаль намного проще, так как вы можете начать в конце и начать свой путь к началу.
Ответ 9
Сначала подсчитайте количество узлов в списке. Затем перейдите снова, считая n меньше узлов. Тем не менее алгоритм O (n), который неизбежен.
Ответ 10
его очень просто..
возьмите два указателя p1, p2
start p2 после того, как p1 переместил "n" узлы и пусть p1 перемещается до последнего. node, на которое указывает p2, будет nth node из последнего
Ответ 11
Этот код кажется более понятным.
public Node<T> findNthNodeFromLast(int n) {
Node<T> current = head;
Node<T> findElement = head;
int length = 0;
while (current != null && current.next != null) {
length++;
if (length >= n) {
findElement = findElement.next;
}
current = current.next;
}
return findElement;
}