Asuma el tamaño de la lista como N ( solo por el bien de la explicación ) . Atravesar 3 nodos es suficiente. 2 no es suficiente debido al Caso 2 y el Caso 3 explicados a continuación.
Deje que los 3 elementos recorridos son a, by c.
Caso 1: punteros dados apuntan a uno de los primeros elementos N – 2 en el orden ordenado. Entonces los 3 elementos estarán en el orden original ordenado . Si a <b <c, el orden ordenado es ascendente ( no decreciente ), de lo contrario es descendente ( no aumenta ) .
- ¿Cómo podemos encontrar el número de subsecuencias consecutivas en una matriz, con la propiedad de que la suma de las subsecuencias es menor que un número k?
- ¿Qué tan importante es conocer los patrones de diseño para entrevistas para un desarrollador experimentado?
- ¿Por qué hay una gran diferencia entre las preguntas de algoritmos en una entrevista técnica y el desarrollo de software real?
- ¿Está obligado a codificar exactamente como lo hace con los compiladores durante las entrevistas técnicas de Google (incluso para los problemas más complejos)?
- Si no puedo resolver problemas de algoritmos en la entrevista técnica, ¿cómo debería fallar la entrevista de una manera excelente?
Caso 2: punteros dados apuntan al último elemento en el orden ordenado. Luego, los dos últimos elementos de los 3 elementos recorridos estarán en el orden ordenado original . Si b <c, el orden ordenado es ascendente ( no decreciente ) , de lo contrario es descendente ( no aumenta ) .
Caso 3: los puntos de puntero dados al último pero un elemento en el orden ordenado. Luego, los dos primeros elementos de los 3 elementos recorridos estarán en el orden ordenado original . Si a <b, el orden ordenado es ascendente ( no decreciente ) , de lo contrario es descendente ( no aumenta ) .
Pero, la pregunta es ¿cómo descubrimos a dónde apunta el puntero? (al último elemento o al último pero uno o ninguno de estos dos).
Paso 1: Si a <b b> c, el puntero apunta a uno de los primeros N – 2 elementos. Si no, vaya al paso 2
Paso 2: si a> b <c <a o a c> a, el puntero apunta al último elemento. Si no, vaya al paso 3.
Paso 3 : si a c b a, el puntero apunta al último elemento pero a uno
Nota: Esta explicación es para la lista que no contiene duplicados, pero es trivial expandirla para la lista con elementos duplicados también. En lugar de atravesar 3 elementos, atraviese hasta obtener 3 elementos distintos .