algorithm - sucesion - termino enesimo wikipedia

¿Cómo encontrar el enésimo elemento desde el final de una lista individualmente vinculada?

Question

La siguiente función es tratar de encontrar el nth elemento de una lista vinculada por separado.

Por ejemplo:

Si los elementos son 8->10->5->7->2->1->5->4->10->10 , el resultado es el 7th hasta el último nodo es 7 .

¿Alguien puede ayudarme sobre cómo funciona este código o hay un enfoque mejor y más simple?

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

¿Qué opinas sobre este enfoque?

1. Cuenta la longitud de la lista enlazada.
2. Índice de nodo real de la cabecera = longitud de la lista de enlaces: índice dado;
3. Escribe una función para travesre desde la cabeza y obtén el nodo en el índice anterior.

Answer 2

Aquí está el código usando el enfoque de 2 punteros: ( source )

Enfoque del puntero lento y más rápido

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

Recursión

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

Answer 3

Aquí está la versión de C # de buscar nth child desde 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;
    }

Answer 4

Aquí tomamos dos punteros pNode y qNode, ambos puntos iniciales para dirigir qNode. Luego, recorra hasta el final de la lista y el pNodo solo atravesará cuando haya una diferencia entre el recuento y la posición que sea mayor que 0 y pthNode incremente una vez en cada ciclo.

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

Answer 5

Como esto suena como tarea, prefiero ayudarte a ayudarte a ti mismo en lugar de dar una solución real.

Sugiero que ejecute este código en un pequeño conjunto de datos de muestra. Use su depurador para ejecutar líneas paso a paso (puede establecer un punto de interrupción al inicio de la función). Esto debería darte una idea de cómo funciona el código.

También puede Console.WriteLine() para generar variables de interés.

Answer 6

Creo que hay un error en el código de la pregunta, y me pregunto si se ha extraído de un libro cómo es posible ... puede que se ejecute correctamente, pero el código es lógicamente incorrecto. Dentro del bucle for ... ¡la condición if debería verificarse contra 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
   }

... el resto está bien y la explicación dada ya cambia el código de las posiciones p2 (n-1) a p1 , luego en el ciclo while las mueve simultáneamente hasta que p2->next llegue al final ... se cayó para decir si encuentra mi respuesta es incorrecta

Answer 7

Dependiendo de la tolerancia de costo de memoria (O (k) en esta solución) podríamos asignar una matriz de punteros de longitud k, y poblarla con los nodos como una matriz circular al atravesar la lista enlazada.

Cuando terminemos de atravesar la lista enlazada, el primer elemento de la matriz (solo asegúrese de calcular correctamente el índice 0 porque es una matriz circular) tendremos la respuesta.

Si el primer elemento de la matriz es nulo, no hay solución a nuestro problema.

Answer 8

El problema que se da en el libro de la carrera profesional es ligeramente diferente. Dice encontrar el enésimo elemento de una lista individualmente vinculada.

Aquí está mi código:

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

Answer 9

En Java voy a usar-

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

Answer 10

La clave de este algoritmo es separar inicialmente dos punteros p1 y p2 por n-1 nodos, por lo que queremos que p2 apunte al (n-1)th nodo desde el inicio de la lista, luego movemos p2 hasta que alcanza el last nodo de la lista. Una vez que p2 llegue al final de la lista, p1 apuntará al n-ésimo nodo desde el final de la lista.

He puesto la explicación en línea como comentarios. Espero eso ayude:

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

Alternativamente, podemos establecer p1 y p2 separados por n nodos en lugar de (n-1) y luego mover p2 hasta el final de la lista en lugar de moverlos hasta el último nodo:

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 11

Nadie aquí notó que la versión de Jonathan lanzará una NullPinterException si el n es más grande que la longitud de LinkedList. Aquí está mi versión:

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

Acabo de hacer pequeños cambios aquí: cuando el nodo n1 avanza, en lugar de verificar si n1 es nulo, compruebo el clima n1.next es nulo, o bien en el ciclo while n1.next lanzará una NullPinterException.

Answer 12

No, no conoce la longitud de la lista enlazada ... Tendrá que ir una vez para obtener la longitud de la lista de likes, por lo que su enfoque es poco eficiente;

Answer 13

Para comprender este problema, debemos hacer una analogía simple con un ejemplo de medición. Digamos que tienes que encontrar el lugar de tu brazo exactamente a 1 metro del dedo medio, ¿cómo medirías? Simplemente tomaría una regla con una longitud de 1 metro y colocaría el extremo superior de esa regla en la punta del dedo medio y la parte inferior del medidor estará exactamente a 1 metro de distancia de la parte superior de su centro. dedo.

Lo que hacemos en este ejemplo será el mismo, solo necesitamos un marco con n-elemento ancho y lo que tenemos que hacer es poner el marco al final de la lista, por lo tanto, el nodo de inicio del cuadro será exactamente n- el elemento th al final de la lista.

Esta es nuestra lista suponiendo que tenemos M elementos en la lista, y nuestro marco con N elemento de ancho;

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

<-- Frame -->

Sin embargo, solo necesitamos los límites del marco, por lo tanto, el límite final del marco eliminará exactamente (N-1) los elementos del límite de inicio del marco. Entonces solo deben almacenar estos elementos de frontera. Vamos a llamarlos A y B;

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

A <- N-Element Wide-> B

Lo primero que tenemos que hacer es encontrar B, que es el final del cuadro.

ListNode<T> b = head;
int count = 1;

while(count < n && b != null) {
    b = b.next;
    count++;
}

Ahora b es el n-ésimo elemento de la matriz, y a está ubicado en HEAD . Entonces, nuestro marco está configurado, lo que haremos es incrementar los nodos de contorno paso por paso hasta que b llegue al final de la lista donde a estará en el n-ésimo elemento;

ListNode<T> a = head;

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

return a;

Para reunir todo, y con los controles HEAD, N <M (donde M es el tamaño de la lista), controles y otras cosas, aquí está el método de solución completo;

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

Answer 14

Puede simplemente recorrer la lista enlazada y obtener el tamaño. Una vez que tenga el tamaño, puede encontrar el n-ésimo término en 2n, que todavía es 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 15

Simplemente invierta la lista enlazada en tiempo lineal y encuentre el elemento kth. Todavía se ejecuta en tiempo lineal.

Answer 16

Solo otra solución a este problema. Aunque la complejidad del tiempo sigue siendo la misma, este código logra la solución en un solo bucle.

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 17

Solución recursiva:

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

Answer 18

Su algoritmo funciona creando primero referencias a dos nodos en su lista vinculada que están separados por N nodos. Por lo tanto, en su ejemplo, si N es 7, entonces establecerá p1 a 8 y p2 a 4.

Luego avanzará cada referencia de nodo al siguiente nodo en la lista hasta que p2 alcance el último elemento en la lista. De nuevo, en su ejemplo, esto será cuando p1 es 5 y p2 es 10. En este punto, p1 se está refiriendo a la N-ésima al último elemento de la lista (por la propiedad de que están separados N nodos).

Answer 19

También puede resolver el problema anterior utilizando tablas hash. Las entradas de la tabla hash son la posición del nodo y la dirección del nodo. Entonces si queremos encontrar el n-nodo desde el final (esto significa m-n + 1 desde el primero donde m es el número de nodos). Ahora cuando ingresamos las entradas de la tabla hash obtenemos la cantidad de nodos. Los pasos son:

1. Pase cada nodo y realice las entradas correspondientes en la tabla hash.

2. Busque el nodo m-n + 1 en la tabla hash, obtenemos la dirección.

La complejidad del tiempo es O (n).

Answer 20

Tengo mi solución recursiva en otro hilo en here

Answer 21

Use dos punteros pTemp y NthNode. Inicialmente, ambos apuntan al nodo principal de la lista. NthNode comienza a moverse solo después de que pTemp hizo n movimientos. De ambos se mueve hacia adelante hasta que pTemp llegue al final de la lista. Como resultado, NthNode apunta al enésimo nodo desde el final de la lista enlazada.

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

Consulte TextBook: "Estructura de datos y algoritmos simplificados en Java"

Answer 22

Ya hay muchas respuestas aquí, pero todas caminan la lista dos veces (ya sea secuencialmente o en paralelo) o usan mucho almacenamiento adicional.

Puede hacer esto mientras recorre la lista solo una vez (más un poco) usando un espacio adicional constante:

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

Esta versión usa 2 punteros adicionales y hace menos que traversals N+n , donde N es la longitud de la lista y n es el argumento.

Si usa M punteros adicionales, puede N+ceil(n/(M-1)) a N+ceil(n/(M-1)) (y debe almacenarlos en un buffer circular)

Answer 23

mi enfoque, lo que creo que es simple y tiene complejidad de tiempo O (n).

Paso 1: Primero obtenga el recuento de la cantidad de nodos. Ejecutar un bucle for desde el primer nodo hasta el último nodo

Paso 2: Una vez que tenga el recuento, aplique matemática simple, por ejemplo, si hemos encontrado el séptimo nodo para el último nodo y el recuento de todos los nodos es 12, entonces (conteo - índice) - 1 dará algún k nodo, hasta el cual Tendrás que atravesar y será el n-ésimo nodo hasta el último nodo. En este caso (12 -7) -1 = 4

Si los elementos son 8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10, el resultado es que el 7º al último nodo es 7, que no es más que el 4º nodo de el principio.

Answer 24

puedes usar una estructura de datos extra ... si es así, será simple ... comienza a empujar todos los nodos a una pila, mantén un contador y explóralos. según su ejemplo, 8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10 comienzan a leer la lista vinculada y comienzan a empujar los nodos o el nodo-> datos hacia un montón. entonces la pila se verá como superior -> {10, 10,4, 5, 1, 2, 7, 5, 10, 8} <- inferior.

Ahora comience a aparecer desde la parte superior de la pila manteniendo un contador = 1 y cada vez que lo hace, aumente el contador en 1, cuando llegue al n-ésimo elemento (en su ejemplo 7mo elemento) deje de aparecer.

nota: esto imprimirá o recuperará los datos / nodos en orden inverso

Answer 25

//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 26

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