Нахождение «N-го узла от конца» связанного списка

Question

Кажется, это верный ответ, но я не уверен, что это действительно лучший способ. Кажется, я посещаю первые 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;
}

Answer 1

Другой способ сделать это, не посещая узлы дважды, выглядит следующим образом:

Создайте пустой массив размера n, указатель на этот массив, начиная с индекса 0, и начните итерацию с начала связанного списка. Каждый раз, когда вы посещаете узел, сохраняйте его в текущем индексе массива и перемещайте указатель массива. Когда вы заполните массив, перевернитесь и перезапишите элементы, которые вы сохранили ранее. Когда вы дойдете до конца списка, указатель будет указывать на элемент n с конца списка.

Но это также просто алгоритм O (n). То, что вы сейчас делаете, прекрасно. Я не вижу веской причины для его изменения.

Answer 2

Запустите два указателя. Переместите первый элемент N вперед, а затем переместите каждый элемент указателя 1. Когда первый указатель достигает конца, второй указатель даст ответ.

РЕДАКТИРОВАТЬ : Да, это в значительной степени тот же код, который приведен в вопросе. Но я чувствую, что псевдокод проясняет ситуацию. Чтобы ответить на этот вопрос, другого пути нет, так как первые N элементы необходимо посетить дважды. Если N мало, это не имеет значения. Если N большое, то второй цикл будет маленьким. Так что это всегда решение O(n).

Answer 3

Поддерживать 2 указателя на n узлах. Когда 1-й указатель достигает хвоста, второй указатель будет указывать на нужный узел.

Код:

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

}

Answer 4

Я использую статическую переменную 'i', которая будет увеличиваться возвращаясь с конца списка. Как в Постановка задачи, мы бы в основном отслеживая N-й элемент, начинающийся с конца связанного списка. Рекурсия помогает нам отслеживать с конца.

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; 
     }

}

Answer 5

Используйте два указателя pTemp и NthNode. Первоначально оба указателя указывают на головной узел списка. NthNode начинает двигаться только после того, как pTemp сделал n ходов. От обоих движется вперед, пока pTemp не достигнет конца списка. В результате NthNode указывает на n-й узел от конца связанного списка.

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;
  }

См. Учебник: «Структура данных и алгоритмы, упрощенные в Java»

Answer 6

    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;   
}

Answer 7

Ваше время работы все еще равно O (n), поэтому я не вижу, что с этим есть какие-либо проблемы.

Концептуально вы можете разделить список на две части: часть перед возвращаемым узлом и часть после. Одна из этих частей должна быть пройдена дважды. Ваша реализация выбрала первое, что не требует дополнительного использования памяти (кроме пары временных переменных).

Кроме того, вы можете создать стек, просмотреть список и поместить каждый элемент в стек, а затем вытолкнуть n элементов. Тогда вы дважды пройдете конец списка, а не начало. Недостатком является то, что список хранится в памяти дважды. (Вы могли бы сделать стек немного умнее, только сохраняя n элементов и удаляя их из нижней части стека при добавлении новых; тогда вы используете только достаточно места для хранения n узлов.)

Я предполагаю, что вы не можете уничтожить список, перевернув его на месте. Тогда это постоянная память, все еще O (n), все еще идущая конец списка дважды.

Answer 8

Этот код кажется более понятным.

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;
}

Answer 9

это очень просто .. взять два указателя p1, p2 начинать p2 после того, как p1 прошел 'n' узлов, и позволить p1 пройти до последнего. Узел, указанный p2, будет n-м узлом из последнего

Answer 10

Сначала посчитайте количество узлов в списке. Затем пройдитесь снова, считая n узлов меньше. Все еще алгоритм O (n), это неизбежно.