一：解题思路
这道题主要有2种解题方法。第一种：利用一个辅助栈，在遍历链表的时候，将链表中所对应的元素相应的入栈，然后在相应的对比栈顶元素和链表的元素。这种方法遍历了2遍单链表，空间上用了一个栈。所以，Time:O(n),Space:O(n)
第二种方法：将单链表翻转一半，然后分别向2边进行对比。所以，所以，Time:O(n),Space:O(1)
二：完整代码示例 (C++版和Java版)
第一种方法C++：
class Solution { public: bool isPalindrome(ListNode* head) { stack<int> stack; for (ListNode* p = head; p != NULL; p = p->next) { stack.push(p->val); } for (ListNode* p = head; p != NULL; p = p->next) { if (p->val != stack.top()) { return false; } stack.pop(); } return true; } };
第一种方法Java:
class Solution { public boolean isPalindrome(ListNode head) { Stack<Integer> stack=new Stack<>(); for(ListNode p=head;p!=null;p=p.next) { stack.push(p.val); } for(ListNode p=head;p!=null;p=p.next) { if(p.val!=stack.pop()) { return false; } } return true; } }
第二种方法C++:
class Solution { public: bool isPalindrome(ListNode* head) { int len = 0; for (ListNode* p = head; p != NULL; p = p->next,len++); ListNode* pre = NULL; ListNode* cur = head; for (int i = 0; i < len / 2; i++) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } if (len % 2 == 1) cur = cur->next; for (; (pre != NULL) && (cur != NULL); pre = pre->next, cur = cur->next) { if (pre->val != cur->val) { return false; } } return true; } };
第二种方法Java：
class Solution { public boolean isPalindrome(ListNode head) { int len=0; for(ListNode p=head;p!=null;p=p.next,len++); ListNode pre=null; ListNode cur=head; for(int i=0;i<len/2;i++) { ListNode next=cur.next; cur.next=pre; pre=cur; cur=next; } if(len%2==1) cur=cur.next; for(;(pre!=null)&&(cur!=null);pre=pre.next,cur=cur.next) { if(pre.val!=cur.val) { return false; } } return true; } }
原文：https://www.cnblogs.com/repinkply/p/12455425.html