linked-list - example - linked list javascript
Una sola lista vinculada es Palindrome o no (14)
Tengo una lista única vinculada. Quiero encontrar que Linked List es Palindrome o no. Lo he implementado de una manera como a continuación.
bool palindromeOrNot(node *head) {
node *tailPointer;
node *headLocal=head;
node *reverseList=reverseLinkedListIteratively(head);
int response=1;
while(headLocal != NULL && reverseList!=NULL) {
if(headLocal->id==reverseList->id) {
headLocal=headLocal->next;
reverseList=reverseList->next;
}
else
return false;
}
if(headLocal == NULL && reverseList==NULL)
return fasle;
else
return true;
}
Estoy invirtiendo la lista enlazada original y luego comparando el nodo por nodo. Si todo está bien, devolveré 1 más devuelve 0.
¿Hay un mejor algoritmo para resolver el problema?
¿Por qué lo haces complejo? Dado que este es un trabajo a domicilio. Puedo simplemente darle una sugerencia simple. Observo que solo comparas los identificadores en tu código. digamos que su identificación es un char, ¿por qué simplemente no atraviesa la lista una vez y almacena los caracteres en una matriz y luego marca el ícono de palindrome ? su camino simplemente invierte la lista enlazada una vez y atraviesa dos veces la lista enlazada, hay tres recorridos en la función.
Cuando comparamos la lista enlazada con la lista invertida, solo podemos realmente necesitar comparar la primera mitad de la lista. Si la primera mitad de la lista normal coincide con la primera mitad si la lista está en reversa, entonces la segunda mitad de la lista normal debe coincidir con la segunda mitad de la lista invertida.
MÉTODO 1 (Utilice una pila)
Una solución simple es usar una pila de nodos de listas. Esto principalmente implica tres pasos.
- Recorre la lista dada de la cabeza a la cola y empuja cada nodo visitado para apilar.
- Atraviesa la lista de nuevo. Para cada nodo visitado, extraiga un nodo de la pila y compare los datos del nodo reventado con el nodo actualmente visitado.
- Si todos los nodos coinciden, devuelve true, else falso.
La complejidad temporal del método anterior es O (n), pero requiere O (n) espacio adicional. Los siguientes métodos lo resuelven con un espacio extra constante.
MÉTODO 2 (Al invertir la lista)
Este método toma O (n) tiempo y O (1) espacio extra.
- Obtener el medio de la lista vinculada.
- Invierta la segunda mitad de la lista enlazada.
- Compruebe si la primera mitad y la segunda mitad son idénticas.
- Construya la lista enlazada original invirtiendo la segunda mitad nuevamente y volviendo a unirla a la primera mitad
MÉTODO 3 (Uso de la recursividad)
Use dos punteros a la izquierda y a la derecha. Muévete hacia la derecha y hacia la izquierda usando la recursión y busca lo siguiente en cada llamada recursiva.
- La sublista es palindrome.
- El valor actual e izquierdo coinciden.
Si ambas condiciones anteriores son verdaderas, entonces devuelve verdadero.
La idea es usar la función llamada pila como contenedor. Recorre recursivamente hasta el final de la lista. Cuando regresemos del último NULL, estaremos en el último nodo. El último nodo que se compara con el primer nodo de la lista.
Para acceder al primer nodo de lista, necesitamos que el encabezado de lista esté disponible en la última llamada de recursión. Por lo tanto, pasamos la cabeza también a la función recursiva. Si ambos coinciden, debemos comparar (2, n-2) nodos. De nuevo, cuando la recursión vuelve a (n-2) nd nodo, necesitamos referencia al 2do nodo desde la cabeza. Avanzamos el puntero de la cabeza en la llamada anterior, para referirnos al siguiente nodo en la lista.
Sin embargo, el truco para identificar el doble puntero. Pasar un solo puntero es tan bueno como pasar por valor, y pasaremos el mismo puntero una y otra vez. Necesitamos pasar la dirección del puntero de la cabeza para reflejar los cambios en las llamadas recursivas de los padres.
Más: geeksforgeeks
Creo que podrías obtener una mejor solución en términos de tener O (1) uso de memoria y la misma velocidad de O (n). Al trabajar con la lista vinculada en su lugar. No es necesario tener que crear una copia invertida de la lista vinculada. Sin embargo, este método destruye la lista. Tendrás que volver a colocarlo en su lugar, pero el tiempo de ejecución seguirá siendo O (n).
El código para la versión rápida de isPalindrome básicamente encuentra el centro de la lista vinculada, luego lógicamente clasifica la lista enlazada en 2 partes. Invierte solo la primera pieza en su lugar y la compara con la otra pieza. La parte mala es que destruye la lista vinculada debido a la inversión en el primer fragmento de la lista vinculada. Sin embargo, puede unir las listas en su lugar y seguir estando en el tiempo O (n).
La función a mirar es isPalindromeFast. Empecé, pero no he terminado las listas de puntos juntos. Puede ejecutar el código en Ir a jugar aquí http://play.golang.org/p/3pb4hxdRIp .
Aquí está el código completo en Go.
package main
import "fmt"
type Node struct {
value string
next *Node
}
func (n *Node) Next() *Node {
return n.next
}
func (n *Node) Value() string {
return n.value
}
func (n *Node) Length() int {
length := 0
linkedList := n
for linkedList != nil {
length += 1
linkedList = linkedList.Next()
}
return length
}
func NewLinkedList(s string) *Node {
if len(s) == 0 {
return nil
}
headNode := &Node{string(s[0]), nil}
currentNode := headNode
for _, v := range s[1:] {
newNode := &Node{string(v), nil}
currentNode.next = newNode
currentNode = newNode
}
return headNode
}
func PrintLinkedList(linkedList *Node) {
for linkedList != nil {
fmt.Println(linkedList)
linkedList = linkedList.Next()
}
}
func ReverseList(linkedList *Node, endPoint int) *Node {
if endPoint == 1 {
return linkedList
}
first, next, lastNode := linkedList, linkedList, linkedList
lastNode = nil
for i := 0; i < endPoint; i++ {
next = first.Next()
first.next = lastNode
lastNode = first
first = next
}
return lastNode
}
// func StitchListsBackTogether(listA, listB, listC *Node, endOfListA int) *Node {
// listAFixed := ReverseList(listA, endOfListA)
// listStart := listAFixed
// for listAFixed.Next() != nil {
// listAFixed = listAFixed.Next()
// }
// listAFixed.next = listB
// return listStart
// }
func IsPalindromeFast(linkedList *Node) bool {
// Uses O(1) space and O(n) time
// However mutates and destroys list, so need to stitch list backtogether. Initial implementation StitchListsBackTogether
length := linkedList.Length()
endOfListA := length / 2
endOfListB := length / 2
if length%2 == 0 {
endOfListB += 1
} else {
endOfListB += 2
}
listA, listB := linkedList, linkedList
for i := 0; i < endOfListB-1; i++ {
listB = listB.Next()
}
listA = ReverseList(listA, endOfListA)
for listA != nil && listB != nil {
if listA.Value() != listB.Value() {
return false
}
listA = listA.Next()
listB = listB.Next()
}
return true
}
func IsPalindromeSlow(linkedList *Node) bool {
//Uses O(1) space and O(n^2) time
startPalidrome, endPalidrome := linkedList, linkedList
for endPalidrome.Next() != nil {
endPalidrome = endPalidrome.Next()
}
for startPalidrome != endPalidrome {
if startPalidrome.Value() != endPalidrome.Value() {
return false
}
if startPalidrome.Next() == endPalidrome {
return true
}
startPalidrome = startPalidrome.Next()
middlePalidrome := startPalidrome
for middlePalidrome.Next() != endPalidrome {
middlePalidrome = middlePalidrome.Next()
}
endPalidrome = middlePalidrome
}
return true
}
func main() {
fmt.Println(IsPalindromeSlow(NewLinkedList("ttoott")))
fmt.Println(IsPalindromeFast(NewLinkedList("ttoott")))
fmt.Println("")
fmt.Println(IsPalindromeSlow(NewLinkedList("ttott")))
fmt.Println(IsPalindromeFast(NewLinkedList("ttott")))
fmt.Println("")
fmt.Println(IsPalindromeSlow(NewLinkedList("hello")))
fmt.Println(IsPalindromeFast(NewLinkedList("hello")))
fmt.Println("")
fmt.Println(IsPalindromeSlow(NewLinkedList("ttto")))
fmt.Println(IsPalindromeFast(NewLinkedList("ttto")))
fmt.Println("")
fmt.Println(IsPalindromeSlow(NewLinkedList("tt")))
fmt.Println(IsPalindromeFast(NewLinkedList("tt")))
fmt.Println("")
fmt.Println(IsPalindromeSlow(NewLinkedList("t")))
fmt.Println(IsPalindromeFast(NewLinkedList("t")))
fmt.Println("")
fmt.Println(IsPalindromeSlow(NewLinkedList("tto3tt")))
fmt.Println(IsPalindromeFast(NewLinkedList("tto3tt")))
fmt.Println("")
}
Aquí está mi solución a este problema. Para probarlo utilicé números enteros en vez de caracteres, por ejemplo, utilicé 1,4,1,4,1 en lugar de "adada". Puedes cambiar int a char y todo debería seguir funcionando
struct Node
{
Node(int in) : data(in) {}
int data;
Node* next;
};
//This function will find recursively call itself until last element and than it will start //comparing. To compare with correct element from the beginning a paramater called pos is used
bool palindromeStart(Node* first, Node* last, size_t pos, size_t middlePos)
{
if (last->next != NULL)
{
if (palindromeStart(first, last->next, pos + 1, middlePos) == false)
return false;
}
size_t curPos = middlePos - pos;
while (curPos--)
first = first->next;
if (first->data != last->data)
return false;
return true;
}
bool isPalindrome(Node* head)
{
Node* n1 = head;
Node* n2 = head;
size_t middlePos = 0;
while (true)
{
if (n2 == nullptr)
{
--middlePos;
break;
}
else if ( n2->next == nullptr)
{
break;
}
n2 = n2->next->next;
n1 = n1->next;
++middlePos;
} // Until now I just find the middle
return palindromeStart(head, n1, 0, middlePos);
}
int main()
{
Node* n = new Node(1);
Node* n1 = new Node(4);
Node* n2 = new Node(4);
Node* n3 = new Node(1);
Node* n4 = new Node(1);
n->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = nullptr;
//n3->next = n4;
//n4->next = nullptr;
std::cout << isPalindrome(n);
}
Solo reverse mitad de la lista enlazada. Y comienza a comparar. No necesita reverse toda la lista vinculada.
Creo que la solución óptima sería NO usar espacio extra, lo que significa NO usar una nueva LL invertida ... la idea es aprovechar la pila de operaciones que utiliza la recursión ... porque cuando la recursión llegó al caso base, Comenzaría a hacer estallar la pila desde el último nodo insertado, que es el último nodo de la LL ... En realidad estoy a la mitad de esto y choqué contra una pared ... de alguna forma, la raíz y el último nodo están desplazados ... ver mi código
public LLNode compare(LLNode root) {
//
// base case, popping opr stack,
// this should be the last node on the linked list
if (root.next == null) {
System.out.printf("Poping stack: %d/n", root.data);
return root;
}
//
// push the functions to the opr stack
System.out.printf("pushing %d to the stack/n", root.next.data);
LLNode last = compare(root.next);
System.out.printf("On the way back: %d, root: %d/n", last.data, root.data);
return root;
}
Y la salida se ve así:
The list looks like this:
1 2 3 4 3 2 1
pushing 2 to the stack
pushing 3 to the stack
pushing 4 to the stack
pushing 3 to the stack
pushing 2 to the stack
pushing 1 to the stack
Poping stack: 1
On the way back: 1, root: 2
On the way back: 2, root: 3
On the way back: 3, root: 4
On the way back: 4, root: 3
On the way back: 3, root: 2
On the way back: 2, root: 1
Si puedes resolverlo, házmelo saber también
A continuación está mi implementación usando vectores. Espero que ayude a alguien.
archivo node.h como se muestra a continuación
#ifndef node_h
#define node_h
class LinkedList
{
private:
struct node
{
int data;
node *next;
};
node *head;
public:
LinkedList ();
node *createNode (int key);
void appendNodeBack (int key);
void printList ();
bool isPalindrome (LinkedList list);
};
#endif
archivo node.cpp a continuación.
#include <vector>
#include "node.h"
LinkedList::LinkedList ():head(NULL) {}
LinkedList::node *LinkedList::createNode (int key)
{
node *newNode = new node;
newNode->data = key;
newNode->next = NULL;
return newNode;
}
void LinkedList::appendNodeBack (int key)
{
node *newNode = createNode (key);
//if tree is empty
if (head == NULL)
{
head = newNode;
return;
}
//if tree is not empty
//traverse to the last node in the list
node *temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
void LinkedList::printList ()
{
//if tree is empty
if (head == NULL)
{
std::cout << "Tree is empty!/n";
return;
}
//if tree not empty
node *temp = head;
while (temp != NULL)
{
std::cout << temp->data<<"-->";
temp = temp->next;
}
std::cout << "NULL/n";
}
bool LinkedList::isPalindrome (LinkedList list)
{
node *temp = head;
unsigned int count = 0;
//push all elements of the list in an array, and count total number of nodes
std::vector<int> array;
while (temp != NULL)
{
count++;
array.push_back (temp->data);
temp = temp->next;
}
bool check = true;
for (unsigned int i = 0, j = array.size() -1; i < j; i++, j--)
{
if (array.at(i) != array.at(j))
check = false;
}
return check;
}
archivo main.cpp a continuación.
#include <iostream>
#include "node.cpp"
int main ()
{
LinkedList list;
list.appendNodeBack (2);
list.appendNodeBack (3);
list.appendNodeBack (11);
list.appendNodeBack (4);
list.appendNodeBack (6);
list.appendNodeBack (4);
list.appendNodeBack (11);
list.appendNodeBack (3);
list.appendNodeBack (2);
list.printList ();
if (list.isPalindrome (list))
std::cout << "List is a palindrome!/n";
else
std::cout << "List is NOT a palindrome!/n";
return 0;
}
Whether a single-linked list is Palindrome or not , también se puede verificar without reversing the linked list
Se puede abordar un enfoque recursivo donde se comparará un puntero que apunta al comienzo de la lista vinculada y otro puntero que regrese de la recursión del último.
Aquí está el pseudo código:
int isPalindrome(**root,*head)
{
if(!head)
return 1;
else
{
int res = isPalindrome(root,head->next);
if(res == 0)
return 0;
int r = (*root)->data == head->data;
*root = (*root)->next;
return r;
}
}
La llamada se hace como: isPalindrome(&root,root);
En java, almacene el valor en la variable de cadena e invierta usando el generador de cadenas
String s = "";
while (node != null){
s = s+ node1.value;
node = node.next;
}
StringBuilder reverseString = new StringBuilder(s);
reverseString = reverseString.reverse();
String s1 = new String(reverseString);
System.out.println(s.equals(s1));
Hay un par de formas de hacerlo. Una de las soluciones puede ser como a continuación:
- Buscar nodo intermedio en una LinkedList determinada
- Reverse segunda mitad
- Entonces, compáralo con la primera mitad
Esta solución tiene una complejidad de tiempo O (n). Aquí hay una implementación de muestra en C #.
// Returns length of a LinkedList
private static int GetLength(Node head)
{
var length = 0;
if (head == null)
return length;
var runner = head;
while (runner != null)
{
length++;
runner = runner.Next;
}
return length;
}
// Compares two LinkedLists
private static bool Compare(Node head1, Node head2)
{
// Get Lengths
var len1 = GetLength(head1);
var len2 = GetLength(head2);
if (len1 != len2)
return false;
var runner1 = head1;
var runner2 = head2;
while (runner1 != null && runner2 != null)
{
if (runner1.Data != runner2.Data)
return false;
runner1 = runner1.Next;
runner2 = runner2.Next;
}
return true;
}
// Reverse a LinkedList
private static Node Reverse(Node head)
{
if (head == null)
return null;
Node prev = null;
Node next;
var current = head;
while (current != null)
{
next = current.Next;
current.Next = prev;
prev = current;
current = next;
}
return prev;
}
private static bool IsPalindrome(Node head)
{
if (head == null)
return false;
if (head.Next == null)
return true;
var slowPrev = head;
var slow = head;
var fast = head;
while (fast != null && fast.Next != null)
{
fast = fast.Next.Next;
slowPrev = slow;
slow = slow.Next;
}
Node firstHalf;
Node secondHalf;
if (fast == null)
{
secondHalf = slow;
slowPrev.Next = null;
firstHalf = head;
}
else
{
secondHalf = slow.Next;
slowPrev.Next = null;
firstHalf = head;
}
return Compare(firstHalf, Reverse(secondHalf));
}
También puede verificarlo usando matrices. Primero recorra la lista de enlaces desde su raíz y almacene el campo de datos de cada nodo en una matriz y luego invierta esa matriz y luego compare los elementos de la matriz uno por uno. A continuación está el programa
bool isPalindrome(Node *head)
{
int i=0,j,n=0,arr1[50],arr2[50];
struct Node *current;
current=head;
while(current!=NULL)
{
arr1[i]=current->data;
i++;
n++;
current=current->next;
}
j=0;
for(i=n-1;i>=0;i--)
{
arr2[j]=arr1[i];
j++;
}
for(i=0;i<n;i++)
{
if(arr1[i]!=arr2[i])
{
return false;
}
}
return true;
}
el programa Python para verificar la lista de entrada vinculada es palíndromo o no
class Node:
def __init__(self, val):
self.data=val
self.next=None
def rec_palindrome(slow, fast):
if fast == None:
# Even number of nodes
return 0, slow
elif fast.next == None:
return -1, slow
else:
res, ptr = rec_palindrome(slow.next, fast.next.next)
if res == -1:
tmp = ptr.next
if tmp.data != slow.data:
return 1, None
else:
return 0, tmp.next
elif res == 1:
return 1, None
elif res == 0:
if ptr.data != slow.data:
return 1, None
else:
return 0, ptr.next
else:
return res, None
class LinkedList:
def __init__(self):
self.head = None
def append(self, node):
if self.head == None:
self.head = node
else:
cur = self.head
while cur.next != None:
cur = cur.next
cur.next = node
def display(self, msg):
print(msg)
cur = self.head
while cur != None:
print("%d" %cur.data, end="")
if cur.next != None:
print("->", end="")
else:
print("")
cur = cur.next
def is_palindrome(self):
res, ptr = rec_palindrome(self.head, self.head)
if res :
print("The input list is NOT palindrome")
else:
print("The input list is palindrome")
if __name__ == "__main__":
print("Pyhton program to check if the input list is palindrome or not")
N = int(input("How many elements?"))
llist = LinkedList()
for i in range(N):
val = int(input("Enter the element of node %d" %(i+1)))
llist.append(Node(val))
llist.display("Input Linked List")
llist.is_palindrome()
example output:
pyhton program to check if the input list is palindrome or not
How many elements?7
Enter the element of node 112
Enter the element of node 245
Enter the element of node 389
Enter the element of node 47
Enter the element of node 589
Enter the element of node 645
Enter the element of node 712
Input Linked List
12->45->89->7->89->45->12
The input list is palindrome
Estoy usando una pila para almacenar los personajes hasta la mitad de la lista. Luego, verifico los personajes en la segunda mitad de la lista contra la parte superior de la pila. Tiempo: O (n), Espacio: O (n / 2)
SinglyLinkedList.prototype.isPalindrome = function() {
var slow = this.head;
var fast = this.head;
var stack = [];
if(!slow) return false;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next
stack.push(slow.element);
slow = slow.next;
}
// check for odd or even list. if even, push the current slow to the stack.
if(fast.next != null) {
stack.push(slow.element);
}
while(slow.next) {
slow = slow.next;
if(stack.pop() !== slow.element) return false;
}
return true;
}