Palindrome Linked List

我会带着你远行 2022-06-09 00:59 171阅读 0赞

LeetCode 234. Palindrome Linked List

Description：

Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

判断一个单链表是不是回文，要求O(n)的时间复杂度和O(1)的空间复杂度。

思路如下：

由于单链表只能沿一个方向遍历，所以不能在头尾设置两个指针进行同时向中遍历，因此根据回文串特性，比较容易想到的思路是将一个单链表从中间分为两部分，后半部分进行单链表反转，反转后与前半部分比较。

代码如下：

/\*\*  
\* Definition for singly-linked list.  
\* struct ListNode \{  
\* int val;  
\* ListNode \*next;  
\* ListNode(int x) : val(x), next(NULL) \{\}  
\* \};  
\*/  
class Solution \{  
public:  
bool isPalindrome(ListNode\* head) \{  
ListNode \*fast = head;  
ListNode \*slow = head;  
while (fast && fast->next)  
\{  
//fast移到末尾，slow移到中间  
fast = fast->next->next;  
slow = slow->next;  
\}  
slow = reverse(slow);//反转后半部分  
fast = head;  
while (slow) //一定要用slow，fast不行，因为fast比slow长  
\{  
if (slow->val != fast->val)  
return false;  
else  
\{  
slow = slow->next;  
fast = fast->next;  
\}  
\}  
return true;  
  
\}  
ListNode\* reverse(ListNode \*head) \{  
ListNode \*pre = NULL;  
while (head)  
\{  
ListNode \*cur = head->next;  
head->next = pre;  
pre = head;  
head = cur;  
\}  
return pre;  
\}  
\};

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Linked List)234. Palindrome Linked List

1.问题 Given the head of a singly linked list, return true if it is a palindrome or f

小咪咪/ 2023年09月24日 18:56/ 0 赞/ 70 阅读

相关 234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome. Follow up: Could you do

布满荆棘的人生/ 2022年08月21日 03:30/ 0 赞/ 24 阅读

相关 LeetCode--234. Palindrome Linked List

Problem： > Given a singly linked list, determine if it is a palindrome. > Follow up:

左手的ㄟ右手/ 2022年08月21日 00:03/ 0 赞/ 46 阅读

相关 234 Palindrome Linked List

题目要求在O(n)时间和O(1)空间内判断一个链表是不是回文的。先将链表分成2部分，然后反转其中一个，在进行比较。 / Definition for sing

矫情吗；*/ 2022年08月04日 04:17/ 0 赞/ 174 阅读

相关 [leetcode]: 234. Palindrome Linked List

1.题目 Given a singly linked list, determine if it is a palindrome. 例如： 1->2->3->2-

红太狼/ 2022年06月14日 11:41/ 0 赞/ 156 阅读

相关 Palindrome Linked List

LeetCode 234. Palindrome Linked List Description： Given a singly linked list, determin

我会带着你远行/ 2022年06月09日 00:59/ 0 赞/ 172 阅读

相关 234.Palindrome Linked List

/\ Given a singly linked list, determine if it is a palindrome. Follow up: C

╰半橙微兮°/ 2022年06月08日 22:22/ 0 赞/ 152 阅读

相关 234. Palindrome Linked List

/ Definition for singly-linked list. struct ListNode { int val

灰太狼/ 2022年04月03日 13:26/ 0 赞/ 176 阅读

相关 [LeetCode] 234. Palindrome Linked List_Easy tag: Linked List

Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->

小咪咪/ 2021年11月16日 07:20/ 0 赞/ 245 阅读

相关 [LeetCode] Palindrome Linked List

[Palindrome Linked List][Palindrome Linked List] Given a singly linked list, determine

比眉伴天荒/ 2021年09月30日 00:20/ 0 赞/ 234 阅读