方法一

思路

因为需要判断是否为回文结构，所以要比较头尾的数据，而链表无法随机查询数据，所以可以先将链表转换成list。

具体步骤

• 首先初始化一个list列表；

• 遍历链表，将链表中的值转移至list中；

• 在list中通过比较头尾的值来判断链表是否为回文结构。

• 代码如下：

  import java.util.*;
  /*
  * public class ListNode {
  *   int val;
  *   ListNode next = null;
  * }
  */
  public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        // n==1，返回true
        if (head.next == null){
            return true;
        }
        List<Integer> nums = new ArrayList<Integer>();
        // 将链表转换成list
        while(head!=null){
            nums.add(head.val);
            head = head.next;
        }
        int i = 0;
        int j = nums.size()-1;
        while(i<j){
            // 不等则返回false
            // 这边有一个坑，如果不适用equals而使用!=的话，在牛客上对于有负数的测试用例可能会无法通过。
            if (!nums.get(i).equals(nums.get(j))){
                return false;
            }
            ++i;
            --j;
        }
        return true;
    }
  }

• 时间复杂度：，两次遍历；

• 空间复杂度：，列表存储数据需要的size为n。

  方法二

  思路

  方法一的空间复杂度为，较大，可以使用快慢指针，快指针的速度为慢指针的两倍，当快指针到达链表尾部时，慢指针到达中间位置，将慢指针之后的部分进行反转，再与前半部分进行比较。

  具体步骤

• 如图：
  

• 代码如下：

  import java.util.*;
  /*
  * public class ListNode {
  *   int val;
  *   ListNode next = null;
  * }
  */
  public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail(ListNode head) {
    ListNode q= head, p= head;
    //通过快慢指针找到中点
    while (q != null && q.next != null) {
        q = q.next.next;
        p = p.next;
    }
    //如果q不为空，说明链表的长度是奇数个
    if (q != null) {
        p = p.next;
    }
    //反转后半部分链表
    p = reverse(p);
  
    q = head;
    while (p != null) {
        //然后比较，判断节点值是否相等
        if (q.val != p.val)
            return false;
        q = q.next;
        p = p.next;
    }
    return true;
  }
  //反转链表
  public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
  }
  }

• 时间复杂度：，遍历链表

• 空间复杂度：，常数级空间复杂度