给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 
，链表中每个节点的值满足 
[编程题]判断一个链表是否为回文结构
public boolean isPail (ListNode head) {
// write code here
if (head==null) return false;
List<Integer> list = new ArrayList<>();
list.add(head.val);
while (head.next != null) {
list.add(head.next.val);
head = head.next;
}
for(int i = 0, j = list.size() - 1; i < list.size(); i++,j--) {
if(!list.get(i).equals(list.get(j))) {
return false;
}
}
return true;
}
编辑于 2024-04-15 18:25:13
回复(0)
public boolean isPail (ListNode head) {
// write code here
// 投个巧转成数组做了
List<Integer> lis = new ArrayList<>();
while(head!=null){
lis.add(head.val);
head = head.next;
}
int start = 0;
int end = lis.size()-1;
for(;start<end;start++,end--){
if(lis.get(start).equals(lis.get(end))){
continue;
}else{
return false;
}
}
return true;
}
发表于 2024-01-20 17:04:11
回复(0)
要判断是否是回文，链表反转后和反转前一致其实就是回文链表，
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) {
ListNode newList = ReverseList(head);
while (head != null) {
if (head.val != newList.val) {
return false;
}
head = head.next;
newList = newList.next;
}
return true;
}
public ListNode ReverseList (ListNode head) {
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode node = new ListNode(cur.val);
node.next=pre;
cur=cur.next;
pre=node;
}
return pre;
}
}
发表于 2023-11-12 23:10:39
回复(0)
理应该是这种方法
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 slow = head;
ListNode fast = head.next;
while(fast!=null&&fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode suffixPart = slow.next;
slow.next = null;
ListNode reverseSuffixPart = reverse(suffixPart);
while(head!=null && reverseSuffixPart!=null) {
if(head.val != reverseSuffixPart.val) return false;
head = head.next;
reverseSuffixPart = reverseSuffixPart.next;
}
return true;
}
public ListNode reverse(ListNode head) {
if(head == null || head.next == null) return head;
ListNode reverseListNode = null;
ListNode tempListNode = null;
while(head!=null) {
tempListNode = head.next;
head.next = reverseListNode;
reverseListNode = head;
head = tempListNode;
}
return reverseListNode;
}
}
发表于 2023-11-04 15:42:12
回复(1)
public class Solution {
public boolean isPail (ListNode head) {
if ( head == null || head.next == null ) return true;
ListNode right = cutList(head);
while ( head != null && right != null ) {
if ( head.val != right.val ) return false;
head = head.next;
right = right.next;
}
// left, right 一样长，或者 right 多一个
return right == null || right.next == null;
}
ListNode cutList(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 找中点
ListNode fast = dummy, slow = dummy;
while ( fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
}
// 断开
ListNode right = slow.next;
slow.next = null;
// 反转right
return reverse(right);
}
ListNode reverse(ListNode head) {
ListNode pre = null, cur = head, nxt = null;
while ( cur != null ) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
发表于 2023-11-03 15:37:51
回复(0)
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) {
if (head == null || head.next == null) {
return true;
}
if (head.next.next == null && head.next.val == head.val) {
return true;
}
ArrayList<Integer> list = new ArrayList<>();
ListNode tail = reverseListNode(head, list);
int i = 0;
while (tail != null) {
if (tail.val == list.get(i)) {
i++;
tail = tail.next;
} else {
return false;
}
}
return true;
}
public ListNode reverseListNode(ListNode head, ArrayList<Integer> list) {
list.add(head.val);//1 2 3 4 5
if (head.next == null || head == null) {
return head;
}
ListNode tail = reverseListNode(head.next, list);
head.next.next = head;
head.next = null;
return tail;
}
}
发表于 2023-10-19 18:48:03
回复(0)
反转节点后与原节点逐一对比:
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 思路1: 反转节点后与原节点逐一对比
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
if(head == null) {
return false;
}
// 反转列表
ListNode rev = revNode(head);
while(rev != null && rev.val == head.val) {
rev = rev.next;
head = head.next;
}
return rev == null;
}
/**
反转列表
*/
public ListNode revNode(ListNode head) {
ListNode cur = null;
ListNode pre = null;
while(head != null) {
cur = new ListNode(head.val);
cur.next = pre;
pre = cur;
head = head.next;
}
return cur;
}
}
发表于 2023-10-15 01:48:35
回复(0)
结合反转例题做
public boolean isPail (ListNode head) {
// write code here
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow = reserve(slow);
fast = head;
while (slow != null) {
if (slow.val != fast.val) {
return false;
} else {
slow = slow.next;
fast = fast.next;
}
}
return true;
}
static ListNode reserve(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
发表于 2023-09-13 18:45:38
回复(0)
public boolean isPail (ListNode head) {
List<Integer> arr = new ArrayList();
ListNode h = head;
while (h != null) {
arr.add(h.val);
h = h.next;
}
for (int i = 0, j = arr.size() - 1; i <= j; i++, j--) {
if (!arr.get(i).equals(arr.get(j))) {
return false;
}
}
return true;
}
发表于 2023-09-13 10:09:35
回复(0)
if(head==null ||head.next==null){
return true;
}
List<Integer> list=new ArrayList<>();
while(head!=null){
list.add(head.val);
head=head.next;
}
int i=0,j=list.size()-1;
while(i<j){
if(!list.get(i).equals(list.get(j)))
{
return false;
}
i++;
j--;
}
return true;
发表于 2023-07-17 18:59:04
回复(0)
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
//1、判断头节点是否为空
if (head == null) {
return true;
}
//2、判断是否只有一个节点
if (head.next == null) {
return true;
}
//找到链表的中间节点
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode cur = slow.next;
ListNode pre = slow;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = pre;
pre = cur;
cur = curNext;
}
fast = head;
slow = pre;
while (fast != slow) {
if (fast.val != slow.val) {
return false;
}
if (fast.next == slow) {
return true;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
}
发表于 2023-07-10 12:47:58
回复(0)
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
ArrayList<Integer> list=new ArrayList<Integer>();
ListNode cur=head;
while(cur!=null){//遍历整个链表到list，就是为了获得整个链表的长度
list.add(cur.val);
cur=cur.next;
}
boolean ans=true;
for(int i=0;i<(list.size()-1)/2;i++){
if(list.get(i)!=(int)list.get(list.size()-1-i)){//注意这里强转为int
ans=false;
break;
}
}
return ans;
}
}
发表于 2023-04-12 20:21:42
回复(2)
public boolean isPail (ListNode head) {
// write code here
List<Integer> list = new ArrayList<Integer>();
while (head != null) {
list.add(head.val);
head = head.next;
}
Integer[] l = new Integer[list.size()];
list.toArray(l);
int start = 0;
int end = list.size() - 1;
while (start < end) {
System.out.println(l[start] + " " + l[end]);
if (!l[start++].equals(l[end--]))
return false;
}
return true;
}
发表于 2023-03-31 16:41:08
回复(0)
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) {
Stack<Integer> stack = new Stack<Integer>();
ListNode i = head;
int len = 0;
while (i != null) {
stack.push(i.val);
i = i.next;
len++;
}
i = head;
while(len-- >0){
if(stack.pop() != i.val) return false;
i=i.next;
}
return true;
}
}
发表于 2023-03-26 15:54:28
回复(1)
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
ArrayList<Integer> list = new ArrayList<Integer>();
ListNode cur = head;
while (cur != null) {
list.add(cur.val);
cur = cur.next;
}
boolean res = true;
for (int i = 0; i < (list.size() - 1) / 2; i++) {
if (list.get(i) != (int)list.get(list.size() - i - 1)) {
res = false;
break;
}
}
return res;
}
}
发表于 2023-03-25 14:59:45
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
