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

Question

Следующая функция пытается найти элементы от nth до last из односвязного списка.

Например:

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

Кто-нибудь может мне помочь, как работает этот код, или есть лучший и более простой подход?

LinkedListNode nthToLast(LinkedListNode head, int n) {
  if (head == null || n < 1) {
    return null;
  }

  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

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

  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}

Answer 1

Ключом к этому алгоритму является установка двух указателей 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;

Answer 2

Ваш алгоритм работает, сначала создавая ссылки на два узла в вашем связанном списке, которые расположены на расстоянии N узлов. Таким образом, в вашем примере, если N равно 7, тогда для p1 будет установлено значение 8, а для p2 - значение 4.

Затем он будет продвигать ссылку на каждый узел на следующий узел в списке, пока p2 не достигнет последнего элемента в списке. Опять же, в вашем примере это будет, когда p1 равно 5, а p2 равно 10. В этот момент p1 ссылается с N на последний элемент в списке (по свойству, что они являются N узлами друг от друга).

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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)) (и хранить их в кольцевом буфере)

Answer 6

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

Answer 7

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

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

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

Answer 8

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

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

Answer 9

Вы можете просто пройтись по связному списку и получить размер. Получив размер, вы можете найти 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;
}

Answer 10

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