一、题目
二、题解
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;
}
}