判断回文链表

题目描述：判断一个普通的链表是否是回文链表，要求时间复杂度O(n)，空间复杂度O(1)

解决思路：

• 最简单的方法是利用栈把链表的前半段压栈，然后出栈与链表的后半段逐个比对。找中间位置的方法是快慢指针。
• 还有一种方法是利用快慢指针找到中间，然后将链表的后半部分反转，再依次进行比较，利用的是链表反转的知识。

import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.Stack; public class Main_ { class ListNode{ public int val; ListNode next = null; public ListNode(int val){ this.val = val; } } //利用栈的思想 public boolean checkPalindrom(ListNode node){ if(node == null) return false; Stack<ListNode> stack = new Stack<>(); ListNode fast = node; ListNode slow = node; while (fast != null && fast.next != null){ stack.push(slow); slow = slow.next; fast = fast.next.next; } //如果为奇数个 if(fast != null) slow = slow.next; while (!stack.isEmpty()){ if(stack.pop().val != slow.val) return false; slow = slow.next; } return true; } //利用链表反转的思想 public boolean checkPalindrom_(ListNode node){ if(node == null) return false; ListNode fast = node; ListNode slow = node; while (fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } while (fast != null) slow = slow.next; ListNode p = slow.next; ListNode q = slow.next.next; slow.next = null; while(p != null){ p.next = slow; slow = p; p = q; if(q.next != null) q = q.next; } while (slow != null){ if(slow.val != node.val) return false; slow = slow.next; node = node.next; } return true; } public static void main(String[] args) { ListNode node1 = new Main_().new ListNode(1); ListNode node2 = new Main_().new ListNode(2); ListNode node3 = new Main_().new ListNode(3); ListNode node4 = new Main_().new ListNode(3); ListNode node5 = new Main_().new ListNode(1); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = null; System.out.println(new Main_().checkPalindrom(node1)); System.out.println(new Main_().checkPalindrom(node1)); } }