234.Palindrome Linked List¶
Tags: Easy
Linked List
Links: https://leetcode.com/problems/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?
/**
* 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) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (!head) return true;
ListNode *dummy = new ListNode(-1);
dummy -> next = head;
ListNode *pre = dummy, *slow = head, *fast = head;
while (fast && fast -> next) {
pre = pre -> next;
slow = slow -> next;
fast = fast -> next -> next;
}
pre -> next = NULL;
slow = reverseLink(slow);
pre = head;
while (pre && slow) {
if (pre -> val != slow -> val) return false;
pre = pre -> next;
slow = slow -> next;
}
return true;
}
ListNode *reverseLink(ListNode *root)
{
ListNode *dummy = new ListNode(-1);
dummy -> next = root;
ListNode *pre = root, *cur = root -> next;
while (cur) {
pre -> next = cur -> next;
cur -> next = dummy -> next;
dummy -> next = cur;
cur = pre -> next;
}
return dummy -> next;
}
};
快慢指针找到中点,然后切割成两端,后半段翻转链表。