NC+LC：判断字符串或链表回文结构
判断回文结构
NC141：判断回文
题目描述
给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。
示例：输入： "absba" 返回值：true
解法1：转换为字符数组进行前后对比
import java.util.*;
public class Solution {
public boolean judge (String str) {
char[] ch = str.toCharArray(); //将字符串转换为字符数组
int len = str.length();
for(int i=0; i<len/2; i++){//对首尾对应元素判断是否相同
if(ch[i] != ch[len-1-i]){
return false;
}
}
return true;
}
} 解法2：利用首尾指针对字符串进行前后对比
import java.util.*;
public class Solution {
public boolean judge (String str) {//使用首尾指针进行判断，空间复杂度为O（1）
// write code here
if(str == null || str.length() == 0)
return false;
int i = 0;//头指针
int j = str.length() - 1;//尾指针
while(i < j){
if(str.charAt(i) != str.charAt(j))//判断指针所指元素是否相同
return false;
i++;
j--;
}
return true;
}
} 解法3：根据栈的先进后出进行判断
import java.util.*;
public class Solution {
public boolean judge (String str) {//使用栈进行判断
// write code here
if(str == null || str.length() == 0)
return false;
char[] ch = str.toCharArray();
Stack<Character> stack = new Stack<Character>();
for(int i = 0; i<ch.length; i++){//先入栈
stack.push(ch[i]);
}
for(int i = 0; i<ch.length; i++){//遍历判断字符元素是否与出栈元素一致
if(ch[i] != stack.pop()){
return false;
}
}
return true;
}
} LC125：验证回文串
示例：
输入: "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串注意：与牛客网不同的是，LeetCode的该题只考虑字母和数字字符，增加了一些无关字符，不是单纯的判断
解法：双指针
- 可以先将无关字符去除，再进行判断，也可以直接在原字符串上进行判断
- Character.isLetterOrDigit()方法可判断字符是否为字母或数字字符
class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int left = 0, right = n - 1;
while (left < right) {
//遇到无关字符就移动指针
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
++left;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
--right;
}
if (left < right) {
//因为可以忽略字母的大小写，所以都转换为小写进行判断
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
++left;
--right;
}
}
return true;
}
} NC96/LC234：判断一个链表是否为回文结构
题目地址：
示例：
输入：[1,2,2,1] 返回值：true 说明：1->2->2->1
解法1：使用栈
思路
先将链表的数值全部入栈，根据先进先出，出栈的顺序就为从后往前链表的顺序，所以遍历链表与出栈元素的值进行比较，出现不相等的值直接返回false，满足回文就返回true
实现代码
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
public boolean isPail (ListNode head) {
// write code here
if(head == null){
return false;
}
ListNode pre = head;
Stack<Integer> stack = new Stack<Integer>();
while(head != null){//先入栈
stack.push(head.val);
head = head.next;
}
while(!stack.empty()){//再遍历判断出栈元素是否与节点值一致
if(pre.val != stack.pop()){
return false;
}
pre = pre.next;
}
return true;
}
} 优化：快慢指针+栈
先利用快慢指针求中点，将后半部分进行入栈，然后遍历前半部分与出栈元素进行比较
public boolean isPail (ListNode head) {
// write code here
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null && fast.next.next!=null){//快慢指针求中点
fast=fast.next.next;
slow=slow.next;
}
Stack<ListNode> stack=new Stack<ListNode>();
while(slow!=null){//将后半部分进行入栈
stack.push(slow);
slow=slow.next;
}
while(!stack.isEmpty()){//将出栈元素与前半部分元素进行对比
if(stack.pop().val!=head.val){
return false;
}
head=head.next;
}
return true;
} 解法2：快慢指针+翻转
思路
- 先利用快慢指针求链表中点，将链表分为前后两部分，然后将后半部分进行翻转，最后将前后两部分从头开始遍历，判断对应元素是否相等
- 如链表1->2->3->2->1，分前后部分为1->2->3和2->1，将后半部分翻转为1->2，在两部分指向null之前进行元素判断
实现代码
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
public boolean isPail (ListNode head) {
// write code here
if(head == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null){//快慢指针求中点
slow = slow.next;
fast = fast.next.next;
}
ListNode reHead = reverseList(slow.next);//将后半部分进行翻转
while(head != null && reHead != null){//前后部分进行遍历比较
if(head.val != reHead.val){
return false;
}
head = head.next;
reHead = reHead.next;
}
return true;
}
public ListNode reverseList(ListNode head){//翻转链表
if(head == null || head.next == null){
return head;
}
ListNode pre = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}