图解LeetCode——234. 回文链表
原创图解LeetCode——234. 回文链表
原创
一、题目
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
二、示例
2.1> 示例 1：
【输入】head = [1,2,2,1] 【输出】true
2.2> 示例 2：
【输入】head = [1,2] 【输出】false
提示：
- 链表中节点数目在范围
[1, 10^5]内 0<= Node.val <=9
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
三、解题思路
3.1> 思路1：转存+双指针
根据题目描述，我们需要判断链表是否是回文链表，那么比较容易想到的一种解题方式就是，我们创建一个额外的数组结构，从头节点开始遍历链表，并将其存储到数组结构中。但是对于链表结构来说，只有遍历到最后一个链表，才可以知道整个链表的长度，那么，我们就选择ArrayList来进行额外数据的存储。
在对比过程中，我们通过双指针的方式，分别从首、尾两个位置开始，依次向中心靠拢对比，当方向不同，则表示不是回文链表，否则就是回文链表了。
3.2> 思路2：倒转链表
除了上面的解题方式之外，我们也可以探究一下是否能实现 O(1) 空间复杂度解决此题。那么，由于ListNode是单向链表结构，所以只能向一个方向移动，所以为了能够改变遍历方式的话，就可以通过改变next的值来倒转链表。
那么我们就可以将整个链表的一半倒转一下，即：将A——>B倒转为A<——B；那么我们就可以从链表的“中心点”作为开始，分别向两侧进行遍历&对比。那么为题来了，怎么知道那个位置是整个链表的“中心点”呢？此处我们就可以采用快慢指针的方式，即：
【慢指针】一次移动一步，即：
slow = slow.next； 【快指针】一次移动两步，即：fast = fast.next.next;
那么当快指针遍历到末尾之后，慢指针就处于了“中心点”范围内了。不过此处还有奇偶数的特殊处理：
【偶数长度链表】slow会处于中心点范围（两个节点）中的右侧节点位置； 【奇数长度链表】slow会处于中心点位置。
具体操作方式，请见下图所示：
四、代码实现
4.1> 实现1：转存+双指针
class Solution {
public boolean isPalindrome(ListNode head) {
List<ListNode> list = new ArrayList();
while(head != null) {
list.add(head);
head = head.next;
}
for (int i = 0; i < list.size()/2; i++)
if (list.get(i).val != list.get(list.size() - i - 1).val)
return false;
return true;
}
}
4.2> 实现2：倒转链表
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head, pre = null;
while(fast != null && fast.next != null) {
ListNode temp = slow.next;
if (pre != null) slow.next = pre;
pre = slow;
slow = temp;
fast = fast.next.next;
}
if (fast != null) slow = slow.next; // 偶数节点
while (slow != null) {
if (pre.val != slow.val) return false;
pre = pre.next;
slow = slow.next;
}
return true;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
