Problem: 234. 回文链表
题目描述
思路
1.定义指针fast,slow分别指向head,int 类型变量n记录链表的长度;
2.将fast指针移动至 n 2 \frac{n}{2} 2n处;
3.若n为奇数则从fast -> next处反转链表;若为偶数则直接从fast位置翻转链表;
4.当fast不为空时,fast与slow每次向后走一步,若其指向的值不相同则返回false否则返回true
复杂度
时间复杂度:
O ( n ) O(n) O(n)
空间复杂度:
O ( 1 ) O(1) O(1)
Code
class Solution {
public:
/**
* Judge the palindromic linked list
*
* @param head The head node of linked list
* @return bool
*/
bool isPalindrome(ListNode* head) {
ListNode* p = head;
ListNode* fast = head;
ListNode* slow = head;
int n = 0;
while (p != nullptr) {
n++;
p = p -> next;
}
for (int i = 0; i < n / 2; ++i) {
fast = fast -> next;
}
if (n % 2 == 0) {
fast = reverse(fast);
} else {
fast = reverse(fast -> next);
}
while (fast != nullptr) {
if (fast -> val != slow -> val) {
return false;
}
fast = fast -> next;
slow = slow -> next;
}
return true;
}
/**
* Reverse the single linked list
*
* @param head The node to be reversed
* @return ListNode*
*/
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* nextP = cur -> next;
cur -> next = pre;
pre = cur;
cur = nextP;
}
return pre;
}
};