Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (52.70%) | 1576 | - |
给你一个单链表的头节点 head
,请你判断该链表是否为回文链表。如果是,返回 true
;否则,返回 false
。
示例 1:
输入:head = [1,2,2,1]
输出:true
示例 2:
输入:head = [1,2]
输出:false
提示:
[1, 105]
内0 <= Node.val <= 9
看了网上很多双指针,数组,栈,哈希算法计算的,都觉得大题小作了,一下看到一个让人眼前一亮的方法,记录一下。
就是通过StringBuilder类,将链表中的值存储再一个StringBuilder中,然后使用equals方法计算stringBuilder和stringBuilder.resverse()的值,结果就是答案。
class Solution {
public boolean isPalindrome(ListNode head) {
StringBuilder stringBuilder = new StringBuilder();
while (head != null) {
stringBuilder.append(head.val);
head = head.next;
}
return stringBuilder.toString().equals(stringBuilder.reverse().toString());
}
}
虽然按照上述问题能解决,但是还是得看一下使用不同的算法实现的方式。
将head链表的值存储在数组中,然后判断。
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否为回文数
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
递归的方法
如果使用递归反向迭代节点,同时使用递归函数外的变量向前迭代,就可以判断链表是否为回文。
指针是先到尾节点,由于递归的特性再从前往后进行比较。frontPointer是递归方法外的指针。若currentNode.val != frontPoint.val 则返回false。反之,frontPinter向前移动并返回true。
算法的正确性在于递归处理节点的顺序是相反的(回顾上面打印的算法),而我们再函数外又记录了一个变量,因此从本质上,我们同时在正向和逆向迭代匹配。
class Solution {
private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) {
return false;
}
if (currentNode.val != frontPointer.val) {
return false;
}
frontPointer = frontPointer.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
frontPointer = head;
return recursivelyCheck(head);
}
}
快慢指针
可以将链表的后半部分反转(修改链表结构),然后将前半部分和后半部分进行比较。比较完成后我们应该将链表回复原样。
步骤:
可以根据快慢指针进行判断,找到中间值(前半部分链表的尾节点)。
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否为回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
哈希法也是比较优秀的,这里复制粘贴代码,我觉得实现起来逻辑比较复杂,可能是还没太多关于哈希计算的知识点积累,后续再来回顾。
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode t=head;
int base = 11, mod = 1000000007;
int left = 0, right = 0, mul = 1;
while(t!=null){
left = (int) (((long) left * base + t.val) % mod);
right = (int) ((right + (long) mul * t.val) % mod);
mul = (int) ((long) mul * base % mod);
t=t.next;
}
return left==right;
}
}