JavaScript 程序检查单链表是否是回文-js教程-PHP中文网

JavaScript 程序检查单链表是否是回文

单向链表是一种线性数据结构，它以不连续的方式存储在内存中，每个块通过保存下一个块的地址（也称为节点）来连接。回文可以解释为一组字符、数字等，并且从正面和背面读起来都是一样的。我们将得到一个单链表，并且必须从正面和背面查找节点存储的值是否相等。

输入

1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null

登录后复制

输出

Yes, the given linked list is a palindrome.

登录后复制

说明

我们可以看到第一个和最后一个节点具有相同的值，第二个和倒数第二个节点具有相同的值，依此类推，与正面和背面距离相同的每个节点具有相同的值。

输入

1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null

登录后复制

输出

No, the given linked list is not a palindrome.

登录后复制

说明

这里，第一个和第二个节点分别等于最后一个和倒数第二个节点，但之后的节点不具有相同的值。

使用堆栈

在这种方法中，我们首先使用该类创建一个链表，然后定义一些基本函数以将数据添加到链表并打印链表中存在的数据。

示例

// class to create the structure of the nodes class Node{ constructor(data){ this.value = data; this.next = null; } } // function to print the linked list function print(head){ var temp = head; var ans = ""; while(temp.next != null){ ans += temp.value; ans += " -> " temp = temp.next } ans += temp.value ans += " -> null" console.log(ans) } // function to add data in linked list function add(data, head, tail){ return tail.next = new Node(data); } // function to find the string is palindrome or not function check(head){ var temp = head; var stack = []; // defining the stack while(temp != null){ stack.push(temp.value); temp = temp.next; } temp = head; while(temp != null){ if(temp.value != stack.pop()){ return false; } temp = temp.next; } return true; } // defining linked list var head = new Node(1) var tail = head tail = add(2,head, tail) tail = add(3,head, tail) tail = add(3,head, tail) tail = add(2,head, tail) tail = add(1,head, tail) console.log("The given linked list is: ") print(head) // calling function to check if the current linked list is a palindrome or not if(check(head)){ console.log("Yes, the given linked list is a palindrome"); } else{ console.log("No, the given linked list is not a palindrome"); }

登录后复制

时间和空间复杂度

上述代码的时间复杂度为 O(N)，其中 N 是链表的长度。

上述代码的空间复杂度为 O(N)，因为我们使用堆栈数据结构来存储其中的元素。

使用递归

在这个方法中，我们首先找到给定链表的长度，然后使用递归遍历到链表的中间。如果给定链表的长度为奇数，我们将返回中间节点的下一个，否则返回中间节点，并且对于每次调用，我们将从递归调用中从后面获取相应的节点。

示例

// class to create the structure of the nodes class Node{ constructor(data){ this.value = data; this.next = null; } } // function to print the linked list function print(head){ var temp = head; var ans = ""; while(temp.next != null){ ans += temp.value; ans += " -> " temp = temp.next } ans += temp.value ans += " -> null" console.log(ans) } // function to add data in linked list function add(data, head, tail){ return tail.next = new Node(data); } // recursive function function recursion(head, number, odd){ if(number == 0){ if(odd){ return head.next; } else{ return head; } } var temp = recursion(head.next, number-1, odd); // if the current value is not equal then don't move to the next node // by this we will not reach null in the end // indicated the not palindrome if(temp.value != head.value){ return temp; } else{ return temp.next; } } // function to check if the given linked list is palindrome or not function check(head){ var temp = head; var len = 0; // finding the length of the given linked list while(temp != null){ len++; temp = temp.next; } // calling the recursion function if(recursion(head, Math.floor(len/2), len & 1) == null){ return true; } else{ return false; } } // defining linked list var head = new Node(1) var tail = head tail = add(2,head, tail) tail = add(3,head, tail) tail = add(4,head, tail) tail = add(3,head, tail) tail = add(2,head, tail) tail = add(1,head, tail) console.log("The given linked list is: ") print(head) // calling function to check if the current linked list is a palindrome or not if(check(head)){ console.log("Yes, the given linked list is a palindrome"); } else{ console.log("No, the given linked list is not a palindrome"); }

登录后复制