这是悦乐书的第196次更新，第202篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第58题（顺位题号是234）。给出一个单链表，确定它是否是回文。例如：
输入：1-> 2
输出：false
输入：1-> 2-> 2-> 1
输出：true
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
获取原链表反转后的新链表，然后使用循环，依次比较两个链表的节点是否相等。反转链表可以借助之前一道反转单链表的题目，可以直接拿过来用。
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode result = reverseList(head);
while (head != null && result != null) {
if (head.val != result.val) {
return false;
}
head = head.next;
result = result.next;
}
return true;
}
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Stack<ListNode> stack = new Stack<>();
while (head != null) {
stack.push(head);
head = head.next;
}
ListNode res = new ListNode(-1);
ListNode temp = res;
while (!stack.isEmpty()) {
temp.next = new ListNode(stack.pop().val);
temp = temp.next;
}
return res.next;
}
03 第二种解法
利用栈先进后去的特点，先将head的每个节点入栈，然后循环判断head的节点值和出栈的值是否相等，只要不相等即可返回false。
public boolean isPalindrome2(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode newHead = new ListNode(-1);
newHead.next = head;
Stack<Integer> stack = new Stack<>();
while (newHead.next != null) {
stack.push(newHead.next.val);
newHead.next = newHead.next.next;
}
while (head != null && !stack.isEmpty()) {
if (head.val != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}
04 第三种解法
先使用双指针同时遍历head节点，找到中间节点的位置，然后将剩下的部分进行反转，然后比较head和反转后的另一半节点值，如果不相等，则说明它不是回文链表。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public boolean isPalindrome3(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) {
slow = slow.next;
}
slow = reverse(slow);
fast = head;
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
05 第四种解法
此解法是利用递归，先声明一个全局变量head1，然后将head1指向head，利用递归获取到head的最后一个节点，然后和head1的第一个节点开始比较，不相等就依次向上返回。如果相等，head1指向其下一个节点，然后和head的上一层节点相比，判断是否相等。
ListNode head1;
public boolean isPalindrome4(ListNode head) {
if(head==null || head.next==null){
return true;
}
head1=head;
return palin(head);
}
private boolean palin(ListNode last) {
if (last.next == null) {
return last.val == head1.val;
}
boolean val = palin(last.next);
if (!val) {
return val;
}
head1 = head1.next;
val = head1.val == last.val;
return val;
}
06 小结
算法专题目前已连续日更超过一个月，算法题文章58+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！