题解 | #链表的回文结构#
链表的回文结构
http://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
方法一：
1、寻找中间结点并且标记起来--此处需要注意偶数个结点需要取两个中间值中的前一个
2、将链表根据中间结点进行分割成两个链表node1和node2
3、将后一个链表node2逆置--三指针法
4、比较node1和逆置后的node2的各个结点的val值
注意一些循环条件以及边界条件限制，具体问题具体分析
此方法时间复杂度o(N)，空间复杂度o(1)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
//因为已经判断过了，所以A中至少有2个结点，分割后至少有1个结点，cur不可能为null
public ListNode reserveNode(ListNode n){
ListNode pre=null;
ListNode cur=n;
ListNode later=cur.next;
while(cur.next!=null){
cur.next=pre;
pre=cur;
cur=later;
later=later.next;
}
cur.next=pre;
return cur;
}
public boolean chkPalindrome(ListNode A) {
//A为空或者A中只有一个结点
if(A==null || A.next==null){ //假设链表为空时，为回文，如果为null直接指向next会报错
return true;
}
//1.找到中间结点
ListNode quick=A;
ListNode slow=A;
ListNode pre=null;
while(quick!=null && quick.next!=null){
pre=slow;
slow=slow.next;
quick=quick.next.next;
}
//如果链表结点个数为偶数个，需要取两个中间值的前一个
if(quick==null){
slow=pre;
}
//2.以slow所在中间值位置，分割链表--成两部分
ListNode node1=A;
ListNode node2=slow.next;
slow.next=null;
//3.逆置node2
node2=reserveNode(node2);
//4.比较node1和node2
ListNode cur1=node1;
ListNode cur2=node2;
while(cur2!=null){
if(cur1.val!=cur2.val){
return false;
}
cur1=cur1.next;
cur2=cur2.next;
}
return true;
}
}
利用题目给出的条件--链表长度小于等于900--给定大小为900的数组即可
空间复杂度也为o(1)，空间复杂度为o(n)
注意要计算链表长度--根据其长度判断是否回文
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
ListNode cur=A;
//1.给定长度为900的数组，存放链表value
int [] arr = new int[900];
int size=0;
while(cur!=null){
arr[size++]=cur.val;
cur=cur.next;
}
//2.判断回文
int left=0;
int right=size-1;
while(left<=right){
if(arr[left]!=arr[right]){
return false;
}
left++;
right--;
}
return true;
}
}
投递美团等公司9个岗位