题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
思路
- 既然要判断链表是否为回文结构,只需要把链表反转,将链表与反转链表一一对应即可
- 当然,这样需要使用反转链表,而且需要复制一个链表,所以可以把链表中的元素倒入数组中倒序复制一份进行逐个对比,这样也可以
代码
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) {
// 代码健壮性检验
if (head == null) {
return false;
}
if (head.next == null) {
return true;
}
// 头节点
ListNode temp1 = head;
ListNode temp2 = new ListNode(-9999);
ListNode flag = temp2;
// 复制一份链表
while (true) {
temp2.next = new ListNode(temp1.val);
if (temp1.next == null) {
break;
}
temp2 = temp2.next;
temp1 = temp1.next;
}
// 将传入的链表反转
ListNode reverseList = reverseList(head);
while (flag.next != null) {
flag = flag.next;
if (flag.val != reverseList.val) {
return false;
}
reverseList = reverseList.next;
}
return true;
}
/**
* 反转链表
*
* @param head 第一个数据节点
* @return com.gewuyou.algorithm.problem.ListNode
* @apiNote
* @since 2022/12/20 10:42
*/
public ListNode reverseList(ListNode head) {
// 代码健壮性检验
if (head == null) {
return null;
}
// 标记当前节点
ListNode current = head;
// 设置前一节点
ListNode previous = null;
while (current != null) {
//记录当前节点的下一个节点
ListNode temp = current.next;
//让当前节点指向前一个节点
current.next = previous;
//将前一个节点设置为当前节点
previous = current;
//将当前节点向下移动
current = temp;
}
// 当当前节点为空时,表示当前节点到原链表尾+1位置了,返回前一个节点即是反转后的链表头
return previous;
}
}