234. 回文链表

234. 回文链表

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

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

思路： 由于回文链表有一个特性，从中间向左右两边扫描结点的值应该是相等的；所以可以先得到中间结点；然后再反转右侧所有结点跟左侧结点对比即可验证是否是回文链表

时间复杂度： O(n)
空间复杂度： O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {

        //1.没有节点或只有一个节点是回文链表
        if(head==null||head.next==null) return true;

        //2.两个节点的情况
        if(head.next.next==null) return (head.val==head.next.val);

        //3.找到中心结点，并反转后半部分
         ListNode middleNd = middleNode(head);
         ListNode rHead = reverseList(middleNd.next);
         ListNode lHead = head;

        //4.遍历反转后的后半部分链表跟前半部分做对比，只要有一个val不相等那就不是回文链表
        while(rHead != null) {
            if(rHead.val != lHead.val) return false;
            rHead = rHead.next;
            lHead = lHead.next;
        }

        //5.来到这里说明是回文链表
        return true;
    }

    /** 
     找到中心结点
     比如：1>2>3>2>1中的3就是中间结点
     */
     private ListNode middleNode(ListNode head) {
        //思路：快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
     }

    /** 
     反转链表
     传入右半部分头结点
     返回反转后的头结点
     比如： 1>2>3>4 反转后 4>3>2>1
     */
     private ListNode reverseList(ListNode head) {
        //迭代法思路：在头结点前面添加一个空结点，每次向后移动一步的同时修改指针指向

        ListNode prev = null;//前指针结点
        ListNode curr = head;//当前指针结点

        while(curr != null) {//不为空说明还没遍历完
            ListNode tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }
        return prev;
     }

}

如果要求不破坏原链表结构怎么做呢 ？

答： 把反转过的右侧链表，再进行一次反转即可