234. 回文链表

题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/submissions/

解题思路：

切成两半，把后半段反转，然后比较两半是否相等。

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public boolean isPalindrome(ListNode head) {
11         if(head==null||head.next==null)
12             return true;
13         ListNode fast = head;
14         ListNode slow = head;
15         while(fast!=null && fast.next!=null)
16         {
17             slow= slow.next;
18             fast = fast.next.next;
19         }
20         if(fast!=null)
21             slow = slow.next;
22         cut(head,slow);
23         return isEqual(head,reverse(slow));
24         
25     }
26     public void cut(ListNode head,ListNode cutnode)
27     {
28         while(head.next!=cutnode)
29         {
30             head= head.next;
31         }
32         head.next = null;
33     }
34     public ListNode reverse(ListNode head)
35     {
36         ListNode pre = null;
37         ListNode sec = null;
38         while(head!=null)
39         {
40             sec = head.next;
41             head.next = pre;
42             pre = head;
43             head = sec;
44         }
45         return pre;
46     }
47     
48    private boolean isEqual(ListNode l1, ListNode l2) {
49     while (l1 != null && l2 != null) {
50         if (l1.val != l2.val) return false;
51         l1 = l1.next;
52         l2 = l2.next;
53     }
54     return true;
55 }
56 }