LeetCode如何判断回文链表
问题描述
回文链表是指从头到尾和从尾到头读取都是相同的链表。例如,给定链表1->2->2->1,返回true。给定链表1->2->3->2->1,返回true。给定链表1->2->3->4,返回false。
解决思路
要判断一个链表是否回文,我们可以采用如下的步骤:
- 找到链表的中间节点。可以使用快慢指针的方式来找到链表的中间节点。快指针每次移动两步,慢指针每次移动一步,当快指针到达链表尾部时,慢指针刚好到达链表中间。
- 将链表的后半部分反转。可以使用迭代或递归的方式来将链表的后半部分反转。
- 比较前后两部分链表是否相同。比较反转后的后半部分链表和原始链表的前半部分是否相同,如果相同,则说明链表是回文的。
- 恢复链表。如果需要将链表恢复成原始链表,则可以再次反转链表的后半部分,然后将其与前半部分合并。
代码示例
public boolean isPalindrome(ListNode head) {
// 找到链表的中间节点
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转链表的后半部分
ListNode prev = null;
ListNode curr = slow;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// 比较前后两部分链表是否相同
ListNode p1 = head;
ListNode p2 = prev;
while (p1 != null && p2 != null) {
if (p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
// 恢复链表
curr = prev;
prev = null;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
slow.next = prev;
return true;
}
以上代码中,我们通过快慢指针找到链表的中间节点,并将链表的后半部分反转。然后逐个比较前后两部分链表的节点的值是否相同,如果有不相同的节点,则链表不是回文的。最后,我们将链表恢复成原始状态。
猜您想看
-
基于linuxthreads-2.0.1如何分析线程的栈
一、线程栈的概...
2023年05月26日 -
微信语音聊天的使用技巧
一、微信语音聊...
2023年05月15日 -
如何使用远程命令登录香橙派开发板
1、准备工作 ...
2023年05月25日 -
在线直播源码开发IOS端问题的解决方法
一、选择合适的...
2023年07月23日 -
网站如何进行SEO优化
一、网站建设网...
2023年05月25日 -
QString字符串的查找与截取方法
QString...
2023年07月22日