当前位置：网站首页>Determine whether the linked list is palindrome structure
Determine whether the linked list is palindrome structure
2022-06-11 22:18:00 【Bright morning light】
1、 subject
Given the head node of a single linked list head, Please judge whether the linked list is palindrome structure .
2、 Ideas
- Method 1 ： Use stack
Ideas ： Traverse the linked list from the beginning , Put the linked list nodes on the stack in turn , The order in which all the data in the stack pops up is the reverse order of the original linked list ; And then go through the list ,
- Method 2 ： Change the original linked list , Need to pay attention to the boundary
Ideas ： First find the midpoint of the list （ If the odd length , Find midpoint ; If the even length , Find the upper midpoint .）, Its next Set to null ; Then reverse the second half of the linked list , Finally, use two pointers , Point to the two headers of the linked list respectively , Compare their values for consistency . Before returning , To restore the second half of the linked list to its original appearance . Even length , The second half of the linked list is in reverse order , One of the two pointers is null , Stop traversing .
3、 Code
C++ edition
/************************************************************************* > File Name: 022. Judge whether the linked list is palindrome structure .cpp > Author: Maureen > Mail: [email protected] > Created Time: 5、 ... and 6/10 20:07:09 2022 ************************************************************************/
#include <iostream>
#include <stack>
using namespace std;
class Node {
public:
int value;
Node *next;
Node(int v) : value(v) {
}
};
// Method 1 ： Make changes to the original linked list
// Time complexity O(n), Spatial complexity O(1)
bool isPalindrome(Node *head) {
if (head == nullptr) return true;
//1. Find the middle node
Node *n1 = head; // Slow pointer
Node *n2 = head; // Quick pointer
while (n2 != nullptr && n2->next != nullptr) {
n1 = n1->next;
n2 = n2->next->next;
}
//2. Flip the second half of the list
n2 = n1->next;
n1->next = nullptr;
Node *next = nullptr;
while (n2 != nullptr) {
next = n2->next;
n2->next = n1;
n1 = n2;
n2 = next;
}
//n1 by The head node of the reverse linked list in the right half
//3. Determine whether the node values of the left and right halves are the same
Node *lhead = head;
Node *rhead = n1;
bool res = true;
while (lhead != nullptr && rhead != nullptr) {
if (lhead->value != rhead->value) {
res = false;
break;
}
lhead = lhead->next;
rhead = rhead->next;
}
//4. Reversed linked list recovery
n2 = n1->next;
n1->next = nullptr;
while (n2 != nullptr) {
next = n2->next;
n2->next = n1;
n1 = n2;
n2 = next;
}
return res;
}
// Method 2 ： Using a container —— Stack , Traversing the linked list , Put the node on the stack , The order in which the stack is flipped is the reverse order of the original linked list , If it is consistent with the original linked list sequence, it is a palindrome
// Extra space complexity : O(n)
bool isPalindrome2(Node *head) {
stack<Node *> sta;
Node *cur = head;
while (cur != nullptr) {
sta.push(cur);
cur = cur->next;
}
cur = head;
while (cur != nullptr) {
if (cur->value != sta.top()->value) return false;
sta.pop();
cur = cur->next;
}
return true;
}
//for test
void printLinkedList(Node *node) {
cout << "Linked list:";
while (node != nullptr) {
cout << node->value << " ";
node = node->next;
}
cout << endl;
}
int main() {
// Linked list is empty.
Node *head = nullptr;
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
// Linked list ： 1
head = new Node(1);
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
// Linked list ：1->1
head = new Node(1);
head->next = new Node(1);
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
// Linked list 1->2->3
head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
// Linked list 1->2->1
head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(1);
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
// Linked list 1->2->3->1
head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(1);
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
// Linked list 1->2->2->1
head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(2);
head->next->next->next = new Node(1);
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
// Linked list 1->2->3->2->1
head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(2);
head->next->next->next->next = new Node(1);
printLinkedList(head);
cout << isPalindrome(head) << " | ";
cout << isPalindrome2(head) << " | " << endl;
printLinkedList(head);
cout << "=============" << endl;
return 0;
}
Java edition
import java.util.Stack;
public class IsPalindromeList {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
// need n extra space
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<Node>();
Node cur = head;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (head != null) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
// need n/2 extra space
public static boolean isPalindrome2(Node head) {
if (head == null || head.next == null) {
return true;
}
Node right = head.next;
Node cur = head;
while (cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
Stack<Node> stack = new Stack<Node>();
while (right != null) {
stack.push(right);
right = right.next;
}
while (!stack.isEmpty()) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
// need O(1) extra space
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
while (n2.next != null && n2.next.next != null) {
// find mid node
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
// n1 Midpoint
n2 = n1.next; // n2 -> right part first node
n1.next = null; // mid.next -> null
Node n3 = null;
while (n2 != null) {
// right part convert
n3 = n2.next; // n3 -> save next node
n2.next = n1; // next of right node convert
n1 = n2; // n1 move
n2 = n3; // n2 move
}
n3 = n1; // n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) {
// check palindrome
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
n1 = n3.next;
n3.next = null;
while (n1 != null) {
// recover list
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
public static void printLinkedList(Node node) {
System.out.print("Linked List: ");
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
}
}
边栏推荐
- SVN本地部署server和cleint 并用阿里云盘自动备份
- R language book learning 03 "in simple terms R language data analysis" - Chapter 7 linear regression model
- C language to achieve eight sorts (2)
- SequenceList顺序表的实现
- Neglected technique: bit operation
- Daily question - Roman numeral to integer
- Go OS module
- Xshell不小心按到ctrl+s造成页面锁定的解决办法
- How to view the installation date of the win system
- Addition without addition, subtraction, multiplication, Division
猜你喜欢
Explain asynchronous tasks in detail: the task of function calculation triggers de duplication
打印机无法打印测试页是什么原因
论文阅读《Dense Visual SLAM for RGB-D Cameras》
Leetcode - day 2
FastAPI 5 - 常用请求及 postman、curl 使用（parameters，x-www-form-urlencoded, raw）
R语言书籍学习03 《深入浅出R语言数据分析》-第七章 线性回归模型
inner join执行计划变了
Tkinter学习笔记(四)
SVN本地部署server和cleint 并用阿里云盘自动备份
NLP - fastText
随机推荐
向线程池提交任务
大学三年应该这样过
3.3 naming rules of test modules
如果重来一次高考，我要好好学数学！
69. square root of X
R语言书籍学习03 《深入浅出R语言数据分析》-第十二章 支持向量机 第十三章 神经网络
Three methods of quick sorting
Win10弹出USB时出现该设备正在使用的解决方法
每日一题-1317. 将整数转换为两个无零整数的和
BUUCTF(5)
超标量处理器设计 姚永斌 第2章 Cache --2.2 小节摘录
R语言书籍学习03 《深入浅出R语言数据分析》-第八章 逻辑回归模型 第九章 聚类模型
MySQL事务简介
移动端——swipe特效之图片时间轴
Unity中使用调用Shell的命令行
打印机无法打印测试页是什么原因
R语言相关文章、文献整理合集（持续更新）
Example of using zypper command
[niuke.com] DP30 [template] 01 Backpack
MATLAB点云处理（二十四）：点云中值滤波（pcmedian）