给定一个单链表的头结点 head，请判断该链表是否为回文结构。
2、思路- 方法一：使用栈
思路：从头遍历一遍链表，将链表结点依次放入栈中，则栈中的数据全部弹出的顺序就是原链表的逆序；然后再遍历链表，
- 方法二：改原链表，需要注意边界
思路：先找到链表的中点（如果奇数长度，找到中点；如果偶数长度，找到上中点。），其 next 设置为空；然后将链表的后半部分逆序，最后使用两个指针，分别指向链表的两个头，比较它们的值是否一致。返回之前，要把后半部分的链表恢复成原来的样子。偶数长度的时候，后半部分链表逆序后，两个指针中有一个为空，就停止遍历。
3、代码 C++ 版#includeJava 版#include using namespace std; class Node { public: int value; Node *next; Node(int v) : value(v) { } }; //方法一：在原链表上进行改动 //时间复杂度O(n)，空间复杂度O(1) bool isPalindrome(Node *head) { if (head == nullptr) return true; //1.找到中间节点 Node *n1 = head; //慢指针 Node *n2 = head; //快指针 while (n2 != nullptr && n2->next != nullptr) { n1 = n1->next; n2 = n2->next->next; } //2.翻转后半部分链表 n2 = n1->next; n1->next = nullptr; Node *next = nullptr; while (n2 != nullptr) { next = n2->next; n2->next = n1; n1 = n2; n2 = next; } //n1 为 右半部分链表反转后的头结点 //3.判断左右两半部分的节点值是否相同 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.翻转后的链表恢复 n2 = n1->next; n1->next = nullptr; while (n2 != nullptr) { next = n2->next; n2->next = n1; n1 = n2; n2 = next; } return res; } //方法二：使用容器——栈，遍历链表，将节点放入栈中，弹栈的顺序即是原链表的逆序，如果与原链表顺序遍历一致就是回文 //额外空间复杂度: O(n) bool isPalindrome2(Node *head) { stack 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() { //链表为空 Node *head = nullptr; printLinkedList(head); cout << isPalindrome(head) << " | "; cout << isPalindrome2(head) << " | " << endl; printLinkedList(head); cout << "=============" << endl; //链表： 1 head = new Node(1); printLinkedList(head); cout << isPalindrome(head) << " | "; cout << isPalindrome2(head) << " | " << endl; printLinkedList(head); cout << "=============" << endl; //链表：1->1 head = new Node(1); head->next = new Node(1); printLinkedList(head); cout << isPalindrome(head) << " | "; cout << isPalindrome2(head) << " | " << endl; printLinkedList(head); cout << "=============" << endl; //链表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; //链表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; //链表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; //链表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; //链表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; }
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 stack = new Stack();
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 stack = new Stack();
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 中点
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("=========================");
}
}
