[leetcode] 234. Palindrome Linked List

[leetcode] 234. Palindrome Linked List

Description

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

Example 1:

Input:

1->2

Output:

false

Example 2: Input:

1->2->2->1

Output:

true

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

分析

题目的意思是：判断一个链表是否是回文的。

很直接的方法就是先找到链表的中点，这可以通过快慢指针获得，然后反转后面的链表。最后分别从中点->next和head出发，挨个的进行比较，这就是下面描述的方法。另一种方法可以用栈空间，在快慢指针寻找中点的过程中，把慢指针遍历的结点压入栈中；找到中点后，我们依次出栈跟后面的链表的值进行比较，可以得到结果，但是这用了栈空间，所以不符合题意。

代码

/** * 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) { if(!head||!head->next) return true; ListNode* slow=head; ListNode* fast=head; while(fast->next&&fast->next->next){ slow=slow->next; fast=fast->next->next; } ListNode* last=slow->next; ListNode* pre=head; while(last->next){ ListNode* temp=last->next; last->next=temp->next; temp->next=slow->next; slow->next=temp; } last=slow->next; while(last){ if(pre->val!=last->val){ return false; } pre=pre->next; last=last->next; } return true; }};

参考文献

​​[LeetCode] Palindrome Linked List 回文链表​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。