题解 | #判断一个链表是否为回文结构#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if(head==null || head.next==null){
            return true;
        }
        ListNode p=head;
        ListNode fHead = new ListNode(-1);
        while(p!=null){
            ListNode temp = new ListNode(p.val);
            temp.next=fHead.next;
            fHead.next=temp;
            p=p.next;
        }
        ListNode q=fHead.next;
        p=head;
        while(p!=null){
            if(p.val!=q.val){
                return false;
            }
            p=p.next;
            q=q.next;
        }
        return true; 
    }
}

解题思路：

头插法可以将一个链表翻转，利用这个特性将原始链表翻转后再挨个比较若存在不等的值则不是回文，否则都遍历到末尾是回文。

实现过程：

1.当链表为空或者只有一个元素肯定是回文

2.定义一个链表头指针，用于指向翻转后的链表

3.头插法实现翻转，即每遇到新结点，先让新结点指向第一个结点即头指针指向的结点，然后让头指针指向新结点

4.从头往后依次比较结点的值是否相等，不相等则提前结束循环返回false

5.都遍历到末尾，返回true。