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

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

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

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

Ключом к этому алгоритму является установка двух указателей p1 и p2 , разделенных n- 1 узлов, поэтому мы хотим, чтобы p2 указывал на (n-1) th узел с начала списка, затем мы перемещаем p2 до он достигает последнего узла списка.Как только 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. Подсчитайте длину связанного списка.
2. Фактический индекс узла из head = длина linkedlist - заданный индекс;
3. Напишите функцию для перехода из head и получения узла по указанному индексу.