[数据结构与算法]LeetCode 234

题目描述：回文链表

给你一个单链表的头节点?head?，请你判断该链表是否为回文链表。如果是，返回?true?；否则，返回?false。

提示：

• 链表中节点数目在范围[1, 105]?内
• 0 <= Node.val <= 9

示例：

输入：head = [1,2,2,1]
输出：true

?题目分析：找到原链表的中间节点并反转中间节点之后的子链表

//偶数个节点的情况
1-->2-->2-->1
中间节点的子链表：2-->1  reverse  1-->2  （记为L2）
原链表：1-->2-->2-->1  （记为L1）

L1:1-->2-->2-->1
L2:1-->2-->null

//奇数个节点的情况
1-->2-->3-->2-->1
中间节点的子链表：3-->2-->1  reverse  1-->2-->3  （记为L2）
原链表：1-->2-->2-->1  （记为L1）

L1:1-->2-->2-->1 
L2:1-->2-->3-->null

• 同时遍历L1与L2，当二者均不为空时，依次取出值判断是否相等，只要有一个不相等就不是回文链表。
• 因为L2的长度一定是小于或者等于原链表的，遍历时若L2指向空，则说明遍历已经结束。

代码实现：

package LeetCode;
//回文链表=中间节点+反转链表
public class Num234 {
    public boolean isPalindrome(ListNode head) {
        //1.找到中间节点
        ListNode middleNode = middleNode(head);
        //2.反转中间节点后的子链表
        ListNode l2 = reverseList(middleNode);
        //3.同时遍历原先链表与l2
        while(l2 != null){
            if (head.val != l2.val){
                return false;
            }
            l2 = l2.next;
            head = head.next;
        }
        return true;
    }
    public ListNode middleNode(ListNode head) {
        //fast 一次走两步
        ListNode fast = head;
        //low一次走一步
        ListNode low = head;
        while(fast != null && fast.next != null){
            low = low.next;
            fast =fast.next.next;
        }
        return low;
    }
    public ListNode reverseList (ListNode head){
        //1、判空
        if (head ==null || head.next == null){
            return head;
        }
        ListNode sec = head.next;
        //2、反转第二个节点之后的子链表
        ListNode newHead = reverseList(head.next);
        //3、处理head与sec关系
        sec.next = head;
        head.next = null;
        return  newHead;
    }
}