问题
如果字符串存储在单链表中,怎么快速判断这个字符串是否是回文字符串?
知识点
快慢指针、链表反转
实现思路
一般方法 复杂度为O(n²)
- 如果字符串存储在数组中,那么只需要判断第一个和最后一个这么一一对应下去,判断字符是否相同,还是比较简单的。
- 如果单链表中存储也参照这种方法,那么可以定义两个指针,一个初始指向头部,一个初始指向尾部,后续依次一个向后指一个依次向前指。这样也能判断是否是回文字符串。但是对于单链表,查找前继节点,需要遍历链表,所以复杂度是O(n²)
复杂度为O(n)的方法
- 如果使用单链表存储,那么第一步需要找到链表的中间节点,这一步需要用到快慢指针
- 第二步需要将单链表的后半部分进行反转,单链表的反转
代码
定义链表结构
@Data
@AllArgsConstructor
public class SinglyLinedNode<T> {
T data;
SinglyLinedNode<T> next;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public SinglyLinedNode<T> getNext() {
return next;
}
public void setNext(SinglyLinedNode<T> next) {
this.next = next;
}
}
@Data
public class SinglyLinkedList<T> {
SinglyLinedNode<T> head;
public void add(SinglyLinedNode<T> t) {
if (t == null) {
return;
}
if (head == null) {
head = t;
return;
}
SinglyLinedNode<T> couser = head;
while (couser.next != null) {
couser = couser.next;
}
couser.next = t;
}
public String getString() {
if (head == null) {
return null;
}
StringBuilder stringBuilder = new StringBuilder();
SinglyLinedNode<T> couser = head;
stringBuilder.append("链表:" + (couser.getData()==null?"null":couser.getData()));
while (couser.next != null) {
couser = couser.next;
stringBuilder.append("->" + (couser.getData()==null?"null":couser.getData()));
}
return stringBuilder.toString();
}
}
从指定的位置反转单链表
static SinglyLinkedList reverseALinkedList(SinglyLinkedList singlyLinkedList, int index) {
if (singlyLinkedList.head == null || singlyLinkedList.head.next == null) {
return singlyLinkedList;
}
if (index <= 0) {
index = 0;
}
SinglyLinedNode cursor = new SinglyLinedNode(null, singlyLinkedList.head);
int temp = 0;
SinglyLinedNode begin = new SinglyLinedNode(null, singlyLinkedList.head);
if (index == 0) {
singlyLinkedList.head = begin;
}
SinglyLinedNode mid = null;
SinglyLinedNode end = null;
while (cursor.next != null) {
cursor = cursor.next;
temp++;
if (temp == index) {
begin = cursor;
}
if (temp - 1 == index) {
mid = cursor;
end = cursor.next;
}
if (temp > index && end != null) {
mid.next = end.next;
end.next = begin.next;
begin.next = end;
cursor = mid;
if (mid.next != null) {
end = mid.next;
}
}
}
if (index == 0) {
singlyLinkedList.head = begin.next;
}
SinglyLinkedList<Object> objectSinglyLinkedList = new SinglyLinkedList<>();
objectSinglyLinkedList.setHead(begin.next);
return objectSinglyLinkedList;
}
最终方法
public class TestHuiWenZiFuChuan {
public static void main(String[] args) {
String testStr = "1";
SinglyLinkedList<Character> singlyLinkedList = transStringToLinkedList(testStr);
System.out.println(singlyLinkedList.getString());
SinglyLinedNode slow = singlyLinkedList.head;
SinglyLinedNode quick = singlyLinkedList.head;
int index = 1;
while (quick.next != null) {
slow = slow.next;
quick = quick.next;
if (quick.next == null) {
break;
}
quick = quick.next;
index++;
}
SinglyLinkedList singlyLinkedList1 = reverseALinkedList(singlyLinkedList, index);
System.out.println("中间位置为:"+index);
System.out.println("从中间反转后原链表:" + singlyLinkedList.getString());
System.out.println("反转后截取的链表:" + singlyLinkedList1.getString());
System.out.println("需要比较的节点数量中间数为"+(index%2==0?"偶数则-1":"奇数则不变")+":"+(index%2==0?index-1:index));
int needConpare=index%2==0?index-1:index;
int hasCompare=0;
SinglyLinedNode<Character> cursor1=new SinglyLinedNode(null,singlyLinkedList.head);
SinglyLinedNode<Character> cursor2=new SinglyLinedNode(null,singlyLinkedList1.head);
for (int i = 0; i <needConpare; i++) {
Character data1 = cursor1.next.data;
Character data = cursor2.next.data;
if (!data1.equals(data)){
System.out.println("\n\n判断结果:"+testStr+"不是回文字符串");
return;
}
}
System.out.println("\n\n判断结果:"+testStr+"是回文字符串");
}
static SinglyLinkedList<Character> transStringToLinkedList(String targetStr) {
if (targetStr == null || targetStr.trim().equals("")) {
return null;
}
char[] chars = targetStr.toCharArray();
SinglyLinkedList<Character> characterSinglyLinkedList = new SinglyLinkedList<>();
for (Character aChar : chars) {
characterSinglyLinkedList.add(new SinglyLinedNode<>(aChar, null));
}
return characterSinglyLinkedList;
}
}