LeetCode [链表] 234.Palindrome Linked List （C++和Python实现）

本文主要是介绍LeetCode [链表] 234.Palindrome Linked List （C++和Python实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

234.Palindrome Linked List [难度：简单]

【题目】

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?

【解题C++】

要求O(n)的时间复杂度和O(1)的空间复杂度。也就是说不能开数组存值。由于链表不能逆着遍历，所以要想通过比较来判断回文与否，那就得先逆转。从哪里逆转是个问题，中点是肯定的。但如果像上道题也就是876题那样处理，会稍微麻烦一些。其实查找中点位置还可以通过快慢指针，和19题是一个思路。这里不需要n，只需要快指针走两步时慢指针走一步即可。

这样看来，这道题的Follow up还是挺综合的，结合了链表逆转T206+中点查找T876（快慢指针T19）。

/*** 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,*slow;fast = slow = head;while(fast){//如果下一步不存在，说明已经到尾结点了 if(fast->next)fast = fast->next->next;else fast = fast->next;slow = slow->next;}//这里的slow其实不是中点，是我们需要逆转的第一个结点。//比如 1,2,3,4,5 slow指向的是4 ListNode* tmp = NULL,*re = NULL;//逆转链表 while(slow){tmp = slow->next;slow->next = re;re = slow;slow = tmp;}//顺序比较 while(re&&head){if(head->val!=re->val)return false;head = head->next;re = re->next;}return true;}
};

【解题Python版】 

思路同C++。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def isPalindrome(self, head: ListNode) -> bool:fast = slow = headwhile fast != None:if fast.next is None:fast = fast.nextelse:fast = fast.next.nextslow = slow.nextnewL = tmp = Nonewhile slow != None:tmp = slow.nextslow.next = newLnewL = slowslow = tmpwhile newL != None and head != None:if newL.val != head.val:return FalsenewL = newL.nexthead = head.nextreturn True

这篇关于LeetCode [链表] 234.Palindrome Linked List （C++和Python实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---