Алгоритм нахождения указателя на узел М Шаги к хвосту в односвязном списке - PullRequest
Новая
       8

Алгоритм нахождения указателя на узел М Шаги к хвосту в односвязном списке

1 голос
/ 20 января 2009

Предположим, что есть односвязный список, длина которого неизвестна. Мы хотим найти узел с M шагами к хвосту.

Например, одиночный список выглядит так: (А) -> (В) -> (С) -> (Х) -> (У) и М = 2. Тогда на выходе должен быть указатель на (C).

Когда я сталкиваюсь с этой викториной, моя первая реакция - пройти по односвязному списку, чтобы получить длину N. Затем пройти по одиночке второй раз, но только вперед N-M-1 шагов. Сложность по времени составляет O (n), а сложность по пространству - O (1).

Тогда мне нужно найти решение, чтобы сделать это одним способом. Решение состоит в том, чтобы иметь два указателя. Второй указатель на М шагов позади первого указателя. Эти два указателя движутся вперед с одинаковой скоростью. Когда первый указатель достигает хвоста, второй указатель является результатом.

После глубокого размышления над этим вопросом я действительно не верю, что второе "хитрое" решение превосходит первое. Это односторонний ход, но он также включает 2 * N-M назначения указателя.

Есть мысли по этому вопросу? Есть ли другое решение, которое действительно быстрее?

Ответы [ 5 ]

3 голосов
/ 20 января 2009

Вы должны использовать кольцевой буфер

Выделите массив указателей M + 1 и заполните (i mod M + 1) -й указатель для каждого узла в списке. Когда вы дойдете до конца, посмотрите M обратно в массиве (оборачиваясь, если вам нужно).

Таким образом, у вас есть только N записей!

Вот пример программы для взлома на c ++ 

node* get_Mth_from_end(node* head, int m)
{
  int pos = 0;
  node** node_array = new node*[m + 1];
  node_array[0] = head;
  while (node_array[(pos + 1) % (m + 1)] = node_array[pos % (m + 1)]->next)
     pos++;
  if (pos < m)
  {
     delete[] node_array;
     return NULL;
  }
  pos = pos - m;
  if (pos < 0)
     pos = pos + m + 1;
  node* retval = node_array[pos];
  delete[] node_array;
  return retval;
}

Это должно быть отключено 1 ошибкой. Мой синтаксис указателя тоже может быть немного неправильным, но идея есть.

0 голосов
/ 20 января 2009

Может быть сделано с N + 4M назначений указателей и пространства журнала (M) (ну, дополнительный пробел, ваш список уже занимает N). Вот как (идея та же самая, которую люди используют в отладчиках возврата). Далее следует псевдокод, где M <2 ^ m, а p - кольцевой буфер длиной m </p> 

for (n=0, front = 0; p[front] != end; ++n, ++p[front]) {
  for (j = 0; j < m; ++j)
    if (n % j = 0)
      ++ front
  front = front % m
}
front = (front-1) % m
for (j = M; j < n-2^m - (n mod 2^m); ++j)
  ++p[front]

p [front] теперь ваш ответ

0 голосов
/ 20 января 2009

Я думаю, что-то немного лучше будет что-то вроде: 

FindNFromEnd(head, n)
    counter = 0;
    first = head
    firstplusn = head
    while (head.next != null)
        counter++
        head = head.next

        if counter == n
            first = firstplusn
            firstplusn = head
            counter = 0

     while counter < n
         counter++
         first = first.next

     return first

например, если n = 3, это будет выглядеть примерно так: 

    0   1   2   3   4   5   6   7
1   FNH
2   FN  H   
3   FN      H
1   F           NH 
2   F           N   H
3   F           N       H
1   F           N           H
2               F           N   H
---
3                  [F]

Таким образом, F отслеживает голову - N - счетчик, N отслеживает голову счетчик, и вам нужно только что-то сделать (N + M + N / M), а не O (2 * N - M).

0 голосов
/ 20 января 2009

Мне нравится рекурсивное предложение. Однако я не верю, что это повысит производительность по сравнению с алгоритмом двойного указателя в этом вопросе.

Rubancache верен в том смысле, что структура данных не поддерживает более быстрые операции. Это сделано для медленных обходов, но с быстрым временем вставки.

0 голосов
/ 20 января 2009

Кроме предложенного вами алгоритма стиля подсчета, вы можете использовать рекурсивную функцию, подобную: 

int getNumNodesAfter(Node *node){
   if( node->next == NULL ){
      return 0;
   }else{
      return getNumNodesAfter(node->next) + 1;
   }
}

Конечно, вы захотите найти хороший способ сохранить рассматриваемый узел, когда функция вернет искомое число.

(Редактировать: это, вероятно, не более эффективно, чем алгоритм подсчета, просто альтернатива)

Реальный ответ на этот вопрос, однако, таков: ваша структура данных (односвязный список) не способствует быстрой реализации операции, которую вы хотите выполнить над ним, поэтому вам следует выбрать новую структуру данных.

...