234.Palindrome Linked List

直观解决方法的空间复杂度为o(n)，判断回文数通常是从两端往中间进行比较。考虑到链表特性及对时间，空间复杂度的要求，有两种思路：

一、将链表一分为二，后半部分翻转，然后依次比较每个元素是否相等。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head==null) return true; ListNode slow = head; ListNode fast = head; while(fast.next!=null && fast.next.next!=null){ slow=slow.next; fast=fast.next.next; } ListNode start = null; slow = slow.next; while(slow!=null){ ListNode temp = slow.next; slow.next = start; start = slow; slow = temp; } while(start!=null){ if(head.val!=start.val) return false; start= start.next; head = head.next; } return true; } }

 二、利用栈的特性

class Solution { ListNode ref; public boolean isPalindrome(ListNode head) { ref = head; return check(head); } public boolean check(ListNode node){ if(node == null) return true; boolean ans = check(node.next); boolean isEqual = (ref.val == node.val)? true : false; ref = ref.next; return ans && isEqual; } } /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null) return true; if(head.next == null) return true; Stack<Integer> stack = new Stack<Integer>(); ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ stack.push(slow.val); slow = slow.next; fast = fast.next.next; } if(fast != null){ slow = slow.next; } while(slow != null){ if(stack.pop() != slow.val){ return false; } slow = slow.next; } return true; } }

此外，可以新建一个反转链表，本质上和栈是一样的。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null) return true; ListNode p = head; ListNode prev = new ListNode(head.val); while(p.next != null){ ListNode temp = new ListNode(p.next.val); temp.next = prev; prev = temp; p = p.next; } ListNode p1 = head; ListNode p2 = prev; while(p1!=null){ if(p1.val != p2.val) return false; p1 = p1.next; p2 = p2.next; } return true; } }