解法一：（由于时间复杂度是O(N*N)，所以遇到很长的链表会超时）
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public boolean isPalindrome(ListNode head) { ListNode shift = head; int length = 0; while(shift != null){ length++; shift = shift.next; } shift = new ListNode(0);//为了循环体的编写，建立一个哨位结点 shift.next = head; for(int i = 1, last = length; i <= length/2; i++, last--){//每次移动后last往前移 //遍历链表，判断第i个结点与第length-i+1个结点是否相同，以此判断链表是否是回文的 //时间复杂度O（N*N），空间复杂度O（1） shift = shift.next; int move = last - i;//向后移动move步到达第length-i+1个结点 ListNode shift2 = shift; while(move > 0){//不是while(move >= 0)，测试时用List = [1,2]即可检查出，简单的测试技巧 shift2 = shift2.next; move--;//记得递减 } if(shift2.val != shift.val){ return false; } } return true; } }解法二：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public boolean isPalindrome(ListNode head) { //用栈和队列来把链表的值重新存放，时间复杂度O(N)，空间复杂度O(N) Stack<ListNode> stack = new Stack<>(); Queue<ListNode> queue = new LinkedList<>(); ListNode temp = head; while(temp != null){ stack.add(temp); queue.add(temp); temp = temp.next; } while(!stack.isEmpty()){ if(stack.pop().val != queue.poll().val){ return false; } } return true; } }