(链表专题) 234. 回文链表——【Leetcode每日一题】

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1,105][1, 10^5][1,105]内
• 0 <= Node.val <= 9

思路：

题目要求：以 O(1) 的空间复杂度来求解。

法一：

• 切成两半，把后半段反转，然后比较两半是否相等

法二：快慢指针

• 快慢指针遍历，边遍历，边反转前半部分
• 然后比较两半是否相等

代码：(Java、C++)

法一：

Java

/*** 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) {int len = 0;ListNode tem = head;ListNode mid = head;while(tem != null){len++;tem = tem.next;if(len % 2 == 0){//找到后半部分头节点mid = mid.next;}}if(len % 2 != 0){mid = mid.next;}//将后半部分反转ListNode pre = mid;mid = null;while(pre != null){tem = pre.next;pre.next = mid;mid = pre;pre = tem;}for(int i = 0; i < len / 2 && mid != head; i++){//比较if(head.val == mid.val){head = head.next;mid = mid.next;}else{return false;}} return true;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {int len = 0;ListNode* tem = head;ListNode* mid = head;while(tem != NULL){len++;tem = tem->next;if(len % 2 == 0){//找到后半部分头节点mid = mid->next;}}if(len % 2 != 0){//如果是奇数个，跳过中间节点mid = mid->next;}//将后半部分反转ListNode* pre = mid;mid = NULL;while(pre != NULL){tem = pre->next;pre->next = mid;mid = pre;pre = tem;}for(int i = 0; i < len / 2 && mid != head; i++){//比较if(head->val == mid->val){head = head->next;mid = mid->next;}else{return false;}} return true;}
};

法二：快慢指针
Java

/*** 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 slow = head, pre = head;ListNode fast = head;head = null;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;//反转前半部分pre.next = head;head = pre;pre = slow;}slow = fast != null ? slow.next : slow;//如果是奇数个就跳过中间那个while(head != null){if(head.val == slow.val){head = head.next;slow = slow.next; }else{return false;}}return true;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {if (head == NULL || head->next == NULL) return true;ListNode* slow = head;ListNode* pre = head;ListNode* fast = head;head = NULL;while(fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;//反转前半部分pre->next = head;head = pre;pre = slow;}slow = fast != NULL ? slow->next : slow;//如果是奇数个就跳过中间那个while(head != NULL){if(head->val == slow->val){head = head->next;slow = slow->next; }else{return false;}}return true;}
};

运行结果：

复杂度分析：

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！