面试必刷TOP101：13、判断一个链表是否为回文结构

一、题目

二、题解

2.1 方法一使用list列表

• 因为需要判断是否为回文结构，所以要比较头尾的数据，而链表无法随机查询数据，所以可以先将链表转换成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;
  }
}

2.2 方法二快慢指针

方法一的空间复杂度为O（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;
}
}