Поиск "Nth node с конца" связанного списка

Ответ 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;
}