Как найти n-й элемент из конца односвязного списка?

ключом к этому алгоритму является установка двух указателей p1 и p2 кроме n-1 первоначально узлы, поэтому мы хотим, чтобы p2 указать (n-1)th узел из начала списка, то мы движемся p2 пока он не достигнет last узел списка. Один раз p2 достигает конца списка p1 будет указывать на N-й узел из конца списка.

я поставил объяснение в строку в качестве комментариев. Надеюсь, это поможет:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nth node from the last..so return it.
   return p1;
 }

кроме того, мы можем набор p1 и p2 кроме n узлов вместо (n-1) а потом двигаться p2 до конца списка вместо перемещения до последнего узла:

LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n ; ++j) { // make then n nodes apart.
    if (p2 == null) {
        return null;
    }
    p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
    p1 = p1.next;
    p2 = p2.next;
}
return p1;

Что вы думаете об этом подходе.

1. подсчет длины linkedlist.
2. фактический индекс узла из head = linkedlist length-заданный индекс;
3. напишите функцию в travesre из head и получите узел по указанному выше индексу.

//this  is the recursive solution


//initial call
find(HEAD,k);

// main function
void find(struct link *temp,int k)
{  
 if( temp->next != NULL)
   find( temp->next, k);
 if((c++) == k)       // c is initially declared as 1 and k is the node to find from last.
  cout<<temp->num<<' ';
}

здесь уже есть много ответов, но все они идут по списку дважды (последовательно или параллельно) или используют много дополнительного хранилища.

вы можете сделать это во время прогулки списке только один раз (плюс немного), используя постоянное дополнительное пространство:

Node *getNthFromEnd(Node *list, int n) {

    if (list == null || n<1) {
        return null; //no such element
    }

    Node *mark1 = list, *mark2 = list, *markend = list;
    int pos1 = 0, pos2 = 0, posend = 0;

    while (markend!=null) {
        if ((posend-pos2)>=(n-1)) {
            mark1=mark2;
            pos1=pos2;
            mark2=markend;
            pos2=posend;
        }
        markend=markend->next;
        ++posend;
    }
    if (posend<n) {
        return null; //not enough elements in the list
    }

    //mark1 and mark2 are n-1 elements apart, and the end is at least
    //1 element after mark2, so mark1 is at least n elements from the end

    while((posend - pos1) > n) {
      mark1 = mark1->next;
      ++pos1;
    }
    return mark1;
}

эта версия использует 2 дополнительных указателя делает меньше, чем N+n обходы, где N это длина списка и n - это аргумент.

если вы используете M дополнительные указатели, вы можете получить что до N+ceil(n/(M-1)) (и вы должны хранить их в кольцевой буфер)

Так это звучит как домашнее задание, я предпочитаю, чтобы помочь вам помочь себе вместо того, чтобы дать реальное решение.

Я предлагаю вам запустить этот код на какой-то небольшой выборке данных. Используйте отладчик для пошагового выполнения строк (вы можете установить точку останова в начале функции). Это должно дать вам представление о том, как работает код.

вы можете Console.WriteLine() для вывода интересующих переменных.

просто еще одно решение этой проблемы. Хотя временная сложность остается прежней, этот код достигает решения в одном цикле.

public Link findKthElementFromEnd(MyLinkedList linkedList, int k)
    {
        Link current = linkedList.getFirst();//current node
        Link currentK = linkedList.getFirst();//node at index k

        int counter = 0;

        while(current.getNext()!=null)
        {
            counter++;

            if(counter>=k)
            {
                currentK = currentK.getNext();
            }

            current = current.getNext();
        }

        //reached end
        return currentK;
    }

просто переверните связанный список в линейном времени и найдите K-й элемент. Он все еще работает в линейном времени.

вы можете просто перебрать linkedlist и получить размер. Как только у вас есть размер, вы можете найти n-й член в 2n, который по-прежнему является O(n).

public T nthToLast(int n) {
    // return null if linkedlist is empty
    if (head == null) return null;

    // declare placeholder where size of linkedlist will be stored
    // we are hoping that size of linkedlist is less than MAX of INT
    int size = 0;

    // This is O(n) for sure
    Node i = head;
    while (i.next != null) {
        size += 1;
        i = i.next;
    }

    // if user chose something outside the size of the linkedlist return null
    if (size < n)
        return null;

    // This is O(n) if n == size
    i = head;
    while(size > n) {
        size--;
        i = i.next;
    }

    // Time complexity = n + n = 2n
    // therefore O(n)

    return i.value;
}

У меня есть рекурсивное решение в другом потоке в StackOverflow здесь

нет вы не знаете длину linkedlist ... Вам придется пройти один раз, чтобы получить длину likedlist, поэтому ваш подход мало эффективен;

мы берем здесь два указателя pNode и qNode, обе начальные точки, чтобы возглавить qNode. Затем пройдите до конца списка, и pNode будет проходить только тогда, когда разница между количеством и позицией больше 0, а pthnode увеличивается один раз в каждом цикле.

static ListNode nthNode(int pos){
ListNode pNode=head;
ListNode qNode=head;
int count =0;
while(qNode!=null){
    count++;
    if(count - pos > 0)
        pNode=pNode.next;
    qNode=qNode.next;
}
return pNode;
}

public int nthFromLast(int n){
    Node current = head;
    Node reference = head;      
    for(int i=0;i<n;i++){
        reference=reference.getNext();
    }
    while(reference != null){
        current = current.getNext();
        reference = reference.getNext();
    }
    return current.getData();
}

используйте два указателя 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"

чтобы понять эту проблему, мы должны сделать простую аналогию с примером измерения. Допустим, вы должны найти место вашей руки, где именно 1 метр от вашего среднего пальца, как бы вы измерили? Вы просто возьмете линейку с длиной 1 метр и поместите верхний конец этой линейки на кончик вашего среднего пальца, а нижний конец метра будет точно на расстоянии 1 метра от верхней части вашего среднего пальца.

что мы делаем в этом примере будет то же самое, нам просто нужен кадр с шириной n-элемента, и то, что нам нужно сделать, это поместить кадр в конец списка, таким образом, начальный узел кадра будет точно n-м элементом в конце списка.

Это наш список, предполагающий, что у нас есть M элементов в списке, и наш фрейм с n элементов в ширину;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

<-- Frame -->

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

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 расположена на глава. Итак, наш фрейм установлен, что мы будем делать, это шаг за шагом увеличивать оба граничных узла до b доходит до конца списка, где a будет n-й-К-последнему элементу;

ListNode<T> a = head;

while(b.next != null) {
    a = a.next;
    b = b.next;
}

return a;

чтобы собрать все, и с проверками головы, 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;
        }
    }
}

вы также можете решить данную проблему с помощью хэш-таблиц.Записи хэш-таблицы-это позиция узла и адрес узла. Поэтому, если мы хотим найти n-й узел с конца(это означает m-n+1 от первого, где m-количество узлов).Теперь, когда мы вводим записи хэш-таблицы, мы получаем количество узлов.Шаги:-

1.Пройдите каждый узел и сделайте соответствующие записи в хэш-таблице.

2.Ищем узел m-n+1 в хэш-таблице получаем адрес.

временная сложность равна O (n).

Я думаю, что есть один недостаток в коде вопроса, и мне интересно, если его взяли из книги, как это возможно... он может выполняться правильно, но код несколько логически неверен. Внутри цикла for... условие if должно быть проверено на p2->next ! = NULL

 for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
       if (p2->next == null) {
       return null; // not found since list size < n
   }

...остальное нормально и объяснение как дано уже код сдвигается p2(n-1) позиции заблаговременно p1, то в то время как петля это переместить их одновременно до p2->next доходит до конца .. выпал на свободу чтобы сказать, если вы найдете мой ответ неправильным

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

вот мой код:

    public void findntolast(int index)
    {
        Node ptr = front; int count = 0;
        while(ptr!=null)
        {
            count++;
            if (count == index)
            {
                front = ptr;
                break;
            }
            ptr = ptr.next;
        }
        Node temp=front;
        while(temp!=null)
        {
            Console.WriteLine(temp.data);
            temp=temp.next;
        }
    }

рекурсивное решение:

Node findKth (Node head, int count, int k) {
    if(head == null)
        return head;
    else {
        Node n =findKth(head.next,count,k);
        count++;

        if(count == k)
            return head;

        return n;
    }
}

вы можете использовать дополнительную структуру данных .. если так, то все будет просто ... начните толкать все узлы в стек, поддерживайте счетчик a pop it. согласно вашему примеру, 8->10->5->7->2->1->5->4->10->10 начните читать связанный список и начать толкать узлы или узел->данные в стек. так что стек будет выглядеть, как топ->{10, 10,4, 5, 1, 2, 7, 5, 10, 8}

теперь начинайте с верхней части стека, сохраняя счетчик=1 и каждый раз, когда вы поп-увеличить счетчик на 1, когда вы достигнете n-го элемента (в вашем примере 7-го элемента), прекратите появляться.

Примечание: это будет печатать или извлекать данные / узлы в обратном порядке

вот код с использованием 2 указателя подхода : (источник)

медленный и быстрый подход указателя

struct node
{
  int data;
  struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
  mynode *ptr1,*ptr2;
  int count;

  if(!head)
  {
    return(NULL);
  }

  ptr1  = head;
  ptr2  = head;
  count = 0;

  while(count < n)
  {
     count++;
     if((ptr1=ptr1->next)==NULL)
     {
        //Length of the linked list less than n. Error.
        return(NULL);
     }
  }

  while((ptr1=ptr1->next)!=NULL)
  {
    ptr2=ptr2->next;
  }

  return(ptr2);
}

рекурсия

node* findNthNode (node* head, int find, int& found){
    if(!head) {
        found = 1;
        return 0;
    }
    node* retval = findNthNode(head->next, find, found);
    if(found==find)
        retval = head;
    found = found + 1;
    return retval;
}

---

мой подход, что я думаю, просто и имеет временную сложность O(n).

Шаг 1: сначала получить количество узлов. Запустите цикл for, начиная с первого узла до последнего узла

Шаг 2: Как только у вас есть счетчик, примените простую математику, например, если мы найдем 7 - й узел до последнего узла, а количество всех узлов равно 12, то (count - index) - 1 даст некоторый K-й узел, до которого вам придется пройти, и это будет n-й узел до последнего узла. В этом случай (12 -7)-1 = 4

Если элементы 8->10->5->7->2->1->5->4->10->10 тогда результат 7-го до последнего узла 7, который ничего, кроме 4-го узла с самого начала.

в java я буду использовать-

public class LL {
  Node head;
  int linksCount;

   LL(){
     head = new Node();
     linksCount = 0;
   }

  //TRAVERSE TO INDEX
  public Node getNodeAt(int index){
    Node temp= head;
    if(index > linksCount){
        System.out.println("index out of bound !");
        return null;
    }
    for(int i=0;i<index && (temp.getNext() != null);i++){
        temp = temp.getNext();
    }
    return temp.getNext();
  }
}

никто здесь не заметил, что версия Джонатана бросит исключение NullPinterException, если n больше длины LinkedList. Вот моя версия:

public Node nth(int n){
        if(head == null || n < 1) return null;

        Node n1 = head;
        Node n2 = head;
        for(int i = 1; i < n; i++){
            if(n1.next == null) return null; 
            n1 = n1.next;
        }

        while (n1.next != null){
            n1 = n1.next;
            n2 = n2.next;
        }
        return n2;
}

Я просто делаю небольшие изменения здесь: когда узел n1 шаг вперед, вместо того, чтобы проверять, является ли N1 нулевым, я проверяю погоду n1.далее-null, или же в цикле while n1.далее будет выбрасывать исключение NullPinterException.

вот C# версия поиска n-го ребенка из Linklist.

public Node GetNthLast(Node head, int n)
    {
        Node current, nth;
        current = nth = head;
        int counter = 0;

        while (current.next != null)
        {
            counter++;
            if (counter % n == 0)
            {
                for (var i = 0; i < n - 1; i++)
                {
                    nth = nth.next;
                }
            }
            current = current.next;
        }
        var remainingCounts = counter % n;
        for (var i = 0; i < remainingCounts; i++)
        {
            nth = nth.next;
        }
        return nth;
    }

в зависимости от допустимой стоимости памяти (O (k) в этом решении) мы могли бы выделить массив указателей длины k и заполнить его узлами в виде кругового массива при обходе связанного списка.

когда мы закончим прохождение связанного списка, первый элемент массива (просто не забудьте правильно вычислить 0-индекс, поскольку это круговой массив), у нас будет ответ.

Если первый элемент массива равен нулю, то нет решения для нашего проблема.