[数据结构与算法]回文数字（LeetCode234）---链表(Java)

思路：先用快慢指针找到中间点，然后把后半部分翻转，然后同时遍历前半部分和后半部分，都一样就是回文链表。

/**
 * 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 boolean isPalindrome(ListNode head) {
        //边界条件 1.如果没有数或者只有一个数
        if(head == null || head.next == null) return true;//只有一个节点是head.next == null
        //如果只有两个数，判断它们的值是否一样
        if(head.next.next == null) return head.val == head.next.val;
        //建立一个快指针
        ListNode fast = head;
        //建立一个慢指针
        ListNode slow = head;
		//如上图蓝色部分，如果链表的个数是奇数fast.next = null就结束
		//如果链表的个数是偶数，fast.next.next = null就遍历结束
        while(fast.next != null && fast.next.next != null){
            //slow走一步
            slow = slow.next;
            //fast走两步
            fast = fast.next.next;
        }

        //反转，反转后newRightHead是右边部分的头节点，slow指向的是中间节点，所以反转部分的头节点是slow.next
        ListNode newRightHead = resverse(slow.next);
        //左边部分的头节点
        ListNode newLeftHead = head;
		//slow是中间节点，如上图当链表的长度为奇数的时候，右边部分会短一些，用右边部分来判断
        while(newRightHead != null ){
            //左右两个部分同时移动，如果遇到值不相等的就返回false
            if(newLeftHead.val != newRightHead.val){ //值不相等
                return false;
            }
            //继续移动
            newRightHead = newRightHead.next;
			 //继续移动
            newLeftHead = newLeftHead.next;

        }
        //都判断完了肯定返回true呀
        return true;
    }
    private ListNode resverse(ListNode head){
        
        if(head == null || head.next == null) return head;

        ListNode newHead = resverse(head.next);

        head.next.next = head;

        head.next = null;

        return newHead;

    }
}

反转链表部分的解析