首页 > 代码库 > 234. Palindrome Linked List
234. Palindrome Linked List
Problem statement
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?
Solution
This is very typical link list problem since it includes two basic and important operations for link list: find middle and reverse the link list.
Generally, we can solve it through three main steps:
- Find the middle of the link list
- Reverse the link list from the next of middle
- Compare head and middle to test if the given link list is a palindrome
Time complexity is O(n), space complexity is 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) { if(head == NULL || head->next == NULL){ return true; } ListNode* mid = find_mid(head); mid->next = reverse(mid->next); ListNode* start = mid->next; mid->next = NULL; while(head && start){ if(head->val != start->val){ return false; } head = head->next; start = start->next; } return true; }private: ListNode* find_mid(ListNode* head){ ListNode* fast = head->next; ListNode* slow = head; while(fast != NULL && fast->next != NULL){ fast = fast->next->next; slow = slow->next; } return slow; }private: ListNode* reverse(ListNode* head){ ListNode* prev = NULL; ListNode* next = NULL; while(head){ next = head->next; head->next = prev; prev = head; head = next; } return prev; }};
234. Palindrome Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。