leetcode
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
- 快慢指针
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *quickNode = head; // 快指针，决定着只遍历链表的一半部分
ListNode *previousNode = NULL;
ListNode *currentNode = head;
// 1. 翻转链表的前半部分
while ( quickNode && quickNode -> next ) {
quickNode = quickNode -> next -> next;
ListNode *temp = currentNode -> next;
currentNode -> next = previousNode;
previousNode = currentNode;
currentNode = temp;
}
if ( quickNode ) {
// 当链表个数为奇数时，此时 quickNode 指向最后一个节点，current 指向中心点
// 需要把 currentNode 往后指一位才能开始比较
currentNode = currentNode -> next;
}
// 此时 previousNode 指向的链表为前半部分的翻转结果，如果是回文链表的话，则 previousNode 和 currentNode 接下来指向的会一摸一样
/*
1 -> 2 -> 3 -> 2 -> 1
2 -> 1 -> 3 -> 2 -> 1
^ ^
previousNode currentNode
*/
// 2. 开始遍历比较
while ( previousNode && currentNode ) {
if ( currentNode -> val != previousNode -> val ) {
return false;
}
currentNode = currentNode -> next;
previousNode = previousNode -> next;
}
return true;
}
};
- 栈
class Solution {
public:
bool isPalindrome(ListNode* head) {
std::stack<ListNode *> stack;
ListNode *quickNode = head; // 快指针，决定着只遍历链表的一半部分
ListNode *currentNode = head;
while ( quickNode && quickNode -> next ) {
if ( currentNode ) {
stack.push( currentNode );
}
currentNode = currentNode -> next;
quickNode = quickNode -> next -> next;
}
if ( quickNode ) {
currentNode = currentNode -> next;
}
while ( currentNode ) {
if ( stack.empty() || !stack.top() || currentNode -> val != stack.top() -> val ) {
return false;
}
currentNode = currentNode -> next;
stack.pop();
}
if ( !stack.empty() ) {
return false;
}
return true;
}
};
- 数组
核心思想：将链表遍历一遍转换为数组，双指针指向数组头尾依次向内遍历
网友评论