234. 回文链表

一. 题目:

二. 思路:

• 快慢指针找到中间结点,反转中间结点以后的链表
• 拿反转之后的链表和前面链表进行比较,如果全都匹配上了就是回文链表了

三. 代码:

class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head==null||head.next==null){
                return true;
            }

            //定义快慢指针
            ListNode slow=head,fast=head;

            //寻找中间结点
            while (fast!=null&&fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            //如果fast不为空，说明链表的长度是奇数个
            if (fast != null) {
                slow = slow.next;
            }

            ListNode lastHead = reverseNode(slow);

            while (lastHead!=null){
                if (lastHead.val!=head.val){
                    return false;
                }
                head=head.next;
                lastHead=lastHead.next;
            }


            return true;
        }

        private ListNode reverseNode(ListNode slow) {
            ListNode pre=null;
            ListNode curr=slow;
            while (curr!=null){
                ListNode temp=curr.next;
                curr.next=pre;
                pre=curr;
                curr=temp;
            }
            return pre;
        }
    }