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




linked-list data-structures (22)

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

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

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

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

Например:

Если элементы 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;
}

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


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

См. TextBook: «Структура данных и алгоритмы, упрощенные в Java»


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

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

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


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

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


Вот код с использованием двух указателей: ( source )

Медленный и быстрый указатель

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

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

Мы берем здесь два указателя 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;
}

мой подход, я считаю простым и имеет временную сложность 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-й узел из начало.


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

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


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

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

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

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

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

Сложность времени - O (n).


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

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

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

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

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

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

Вот версия C # для поиска n-го дочернего элемента из списка ссылок.

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

Никто здесь не заметил, что версия Джонатана вызовет исключение 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 имеет значение null, я проверяю, что погода n1.next равно null, иначе в цикле n1.next будет генерировать исключение NullPinterException.


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

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

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

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


dimo414, генерация факторов обычно считается очень сложной задачей. На самом деле защита большинства ваших важных активов (например, денег, информации и т. Д.) Основывается на простой, но чрезвычайно сложной задаче факторизации числа. См. Эту статью о схеме шифрования RSA http://en.wikipedia.org/wiki/RSA_(cryptosystem) . Я отвлекся.

Чтобы ответить на ваш вопрос, комбинаторный подход - ваш лучший метод, на который указывает Никита (кстати, слава в вашем объяснении).

Я знаю, что я мог бы просто перейти от 2 до sqrt (n) и найти все делимые числа

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

Теперь, чтобы определить число факторов для любого заданного числа n, мы рассмотрим простую факторизацию n . Если n = p a , то мы знаем, что n будет иметь ( a + 1 ) множителей ( 1, p, p 2 , ..., p a ). Это ключ к определению общего количества факторов. Если п имел несколько простых факторов, скажем

n = p 1 a · p 2 b ... p p r

затем, используя правило подсчета продуктов ( http://en.wikipedia.org/wiki/Rule_of_product ), мы знаем, что

m = ( a + 1 ) · ( b + 1 ) ... ( r + 1 )

факторы. Теперь все, что нам нужно сделать, - это найти любую возможную комбинацию чисел, данных нам простой разложением. Ниже приведен некоторый код на R, который, надеюсь, демонстрирует то, что я объяснил.

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

n = p 1 a · p 2 b ... p p r

Затем я нахожу только уникальные простые числа, помеченные UniPrimes, поэтому для этого примера UniPrimes будет содержать ( p 1 , p 2 , p k ). Затем я нахожу все силы каждого простого числа и добавляю его в массив с пометкой MyFactors. После создания этого массива я нахожу все возможные комбинации продуктов из элементов в MyFactors. Наконец, я добавляю 1 к массиву (поскольку это тривиальный фактор) и сортирую его. Вуаля! Это очень быстро и работает для очень больших чисел со многими факторами.

Я пытался сделать код максимально переводимым на другие языки (т.е. я предполагаю, что вы уже создали функцию, которая генерирует простую факторизацию (или использует встроенную функцию) и тестовую функцию простого числа.), И я не стал t использовать специализированные встроенные функции, уникальные для R. Дайте мне знать, если что-то не понятно. Ура!

factor2 <- function(MyN) {

    CheckPrime <- isPrime(MyN)

    if (CheckPrime == F && !(MyN == 1)) {
            MyPrimes <- primeFactors(MyN)
            MyFactors <- vector()
            MyPowers <- vector()
            UniPrimes <- unique(MyPrimes)
                    for (i in 1:length(UniPrimes)) {

                            TempSize <- length(which(MyPrimes == UniPrimes[i]))

                            for (j in 1:TempSize) {
                                    temp <- UniPrimes[i]^j
                                    MyPowers <- c(MyPowers, temp)
                            }

                    }
            MyFactors <- c(MyFactors, MyPowers)
            MyTemp <- MyPowers
            MyTemp2 <- vector()
            r <- 2
            while (r <= length(UniPrimes)) {

                    i <- 1L

                    while (i <= length(MyTemp)) {
                            a <- which(MyPrimes >  max(primeFactors(MyTemp[i])))
                                    for (j in a) {
                                            temp <- MyTemp[i]*MyPowers[j]
                                            MyFactors <- c(MyFactors, temp)
                                            MyTemp2 <- c(MyTemp2, temp)
                                    }
                            i <- i + 1
                    }
                    MyTemp <- MyTemp2
                    MyTemp2 <- vector()
                    r <- r + 1
            }
    } else {
            if (MyN == 1) {
                    MyFactors <- vector()
            } else {
                    MyFactors <- MyN
            }
    }
    MyFactors <- c(1, MyFactors)
    sort(MyFactors)
}






algorithm linked-list data-structures