算法系列-力扣234-回文链表判定

回文链表判定

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

方法一：栈反转对比法

解题思路：找到中间节点后用栈辅助反转对比
解题方法：
找到链表的中间节点并判断奇数还是偶数
头结点到中间节点前的节点入栈，偶数从中间节点开始和栈内元素进行比较；
奇数从中间节点后面的节点开始和栈内元素进行比较；
若比较到最后一个节点都相等该链表为回文链表（栈空或比较到最后一个节点）
时间复杂度：O(n)
空间复杂度：O(n)

import java.util.List;
import java.util.Stack;import javax.management.ListenerNotFoundException;/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public static boolean isPalindrome(ListNode head) {/*** head -> 1 -> 2 -> 2 -> 1 -> null* head -> 1 -> 2 -> 1 -> null* 找到链表的中间节点并判断奇数还是偶数* 头结点到中间节点的节点入栈，偶数从中间节点开始和栈内元素进行比较；* 奇数从中间节点后面的节点开始和栈内元素进行比较；* 若比较到最后一个节点都相当该链表为回文链表（栈空或比较到最后一个节点）*/if(head == null){return false;}ListNode dummy = new ListNode(-1);dummy.next=head;ListNode slow=dummy;ListNode fast=dummy;ListNode midNode=null;Boolean isEvent=true;while (fast.next!=null){slow=slow.next;if(fast.next.next!=null) {fast = fast.next.next;} else{fast=fast.next;isEvent=false;}}midNode = isEvent ? slow.next : slow;Stack<ListNode> stack=new Stack<>();ListNode p=dummy.next;while(p!=midNode){stack.push(p);p=p.next;}ListNode m=isEvent?midNode:midNode.next;while(m!=null){ListNode tmp=stack.pop();if(m.val!=tmp.val){return false;}m=m.next;}return true;}
}

方法二：链自反转对比法

解题思路：找到中间节点后用栈辅助反转对比
解题方法：
找到链表的中间节点并判断奇数还是偶数
继续利用双指针反转中间节点前的链表。
偶数从中间节点开始和反转链进行比较；
奇数从中间节点后面的节点开始和反转链进行比较；
若比较到最后一个节点都相等该链表为回文链表（栈空或比较到最后一个节点）
时间复杂度：O(n)
空间复杂度：O(1)

   public static boolean isPalindrome(ListNode head) {/*** [1,0,1]* head -> 1 -> 2 -> 2 -> 1 -> null* head -> 1 -> 2 -> 1 -> null找到链表的中间节点并判断奇数还是偶数继续利用头插法反转中间节点前的链表。偶数从中间节点开始和反转链进行比较；奇数从中间节点后面的节点开始和反转链进行比较；若比较到最后一个节点都相等该链表为回文链表（栈空或比较到最后一个节点）*/if(head == null){return false;}ListNode dummy = new ListNode(-1);dummy.next=head;ListNode slow=dummy;ListNode fast=dummy;ListNode midNode=null;Boolean isEvent=true;while (fast.next!=null){slow=slow.next;if(fast.next.next!=null) {fast = fast.next.next;} else{fast=fast.next;isEvent=false;}}midNode = isEvent ? slow.next : slow;ListNode p = head;head=null;while (p!=midNode){ListNode tmp=p.next;p.next=head;head=p;p=tmp;}//偶数从中间节点开始和反转链进行比较ListNode m = isEvent ? midNode : midNode.next;boolean isPalindrome=true;p=head;while (isPalindrome && p!=null){if(p.val!=m.val){isPalindrome=false;}p=p.next;m=m.next;}// 还原链表p = head;head=midNode;while (p!=null){ListNode tmp=p.next;p.next=head;head=p;p=tmp;}return  isPalindrome;}