两种方法解答
方法一:辅助数组
方法二:快慢指针,翻转链表
import java.util.*;
/*
- public class ListNode {
- int val;
- ListNode next = null;
- } */
public class Solution {
//翻转链表
public ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
ListNode cur_next = null;
while(cur!=null){
cur_next = cur.next;
cur.next = pre;
pre = cur;
cur = cur_next;
}
return pre;
}
public boolean isPail (ListNode head) {
// write code here
// 方法一 辅助数组
ArrayList<Integer> arr = new ArrayList<>();
while(head!=null){
arr.add(head.val);
head = head.next;
}
int index=0, len = arr.size();
int mid=len/2;
while(index<mid){
if(!arr.get(index).equals(arr.get(len-index-1)))
return false;
index++;
}
return true;
//方法二 先通过快慢指针法寻找链表中点,将链表分为左右两份,接着将第二份链表翻转,最后比较
if(head==null || head.next==null)
return true;
ListNode slow = head;
ListNode fast = head.next;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
ListNode right_head = slow.next;
slow.next = null;
ListNode left = head;
ListNode right = reverse(right_head);
while(right!=null){//要么左右结点个数相等,要么左边比右边结点数多一个,所以判断右边就可以了
if(left.val!=right.val)
return false;
left = left.next;
right = right.next;
}
return true;
}
}