大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说【数组、双指针】day7_234. 回文链表,希望您对编程的造诣更进一步.
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入： head = [1,2,2,1]
输出： true
示例 2：
输入： head = [1,2]
输出： false
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
题解
题解一：
思路：遍历链表，使用集合存储链表节点值，比较集合内部前半段和后半段值是否相等
时间复杂度：O(n) 空间复杂度：O(n)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
while(head != null){
list.add(head.val);
head = head.next;
}
for(int i = 0; i < list.size()/2; i ++){
if(list.get(i) != list.get(list.size()-1-i)){
return false;
}
}
return true;
}
}
题解二：
思路：双指针
1、定于一个快慢指针，快指针每次走两步，慢指针每次走一步（链表长度为偶数时，快指针走到null时，慢指针刚好走到后半段的第一个位置；长度为奇数时，快指针走到最后一个位置时，慢指针刚好走到最中间位置）
2、翻转慢指针走过的轨迹，并与慢指针后半段比较
时间复杂度：O(n) 空间复杂度：O(n)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
//快慢指针
ListNode fast = head;
ListNode slow = head;
// 记录slow走过的路径,并且反转一下
ListNode p = null;
ListNode pre = null;
while(fast != null && fast.next != null){
p = slow;
fast = fast.next.next;
slow = slow.next;
p.next = pre;
pre = p;
}
// 当链表长度为奇数时，slow正好走到最中间位置
if(fast != null){
slow = slow.next;
}
//将翻转过的前半段链表与后半段相比较
while(p != null && slow != null){
if(p.val != slow.val){
return false;
}
p = p.next;
slow = slow.next;
}
return true;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/36786.html
