题目链接:234. 回文链表
Ideas
算法:双指针
数据结构:链表
思路:首先把链表的后半段翻转过来,然后用两个指针分别从头和从中间开始遍历判断是否相同,如果相同则是回文链表,否则不是回文链表,但不管是不是回文链表,翻转的链表还是要翻转回去。
1.用快慢指针,快指针quick一次走两步,慢指针slow一次走一步,当快指针到头时,慢指针正好到链表中间;(如果链表长度为奇数,快指针最终走到最后一个元素,如果链表长度为偶数,快指针最终走到倒数第二个元素)
2.从链表中间开始,将后面的节点逐个翻转,即当前节点原本指向下一个节点,改为指向前一个节点;
3.双指针分别从链表的头尾出发,遍历判断当前节点值是否相等,最终双指针相遇时截止;
4.从链表中间开始,再将后面的节点翻转回去。
Code
C++
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
// 1.快慢指针找到链表中间位置
ListNode *quick = head, *slow = head;
while (quick->next != nullptr && quick->next->next != nullptr) {
slow = slow->next;
quick = quick->next->next;
}
// 2.从链表中间位置开始将后续节点翻转
ListNode *cur = slow->next;
slow->next = nullptr;
while (cur != nullptr) {
ListNode *nxt = cur->next;
cur->next = slow;
slow = cur;
cur = nxt;
}
// 3.双指针分别从头尾开始遍历
bool res = true;
quick = head;
ListNode *tail = slow;
while (quick != nullptr && slow != nullptr) {
if (quick->val != slow->val) {
res = false;
break;
}
quick = quick->next;
slow = slow->next;
}
// 4.将翻转的节点再翻转回去
cur = tail->next;
tail->next = nullptr;
while (cur != nullptr) {
ListNode *nxt = cur->next;
cur->next = tail;
tail = cur;
cur = nxt;
}
return res;
}
};
当然,如果你觉得双指针比较麻烦的话,也可以遍历链表保存到数组中再判断是否为回文。
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> values;
while (head) {
values.push_back(head->val);
head = head->next;
}
for (int i = 0, j = values.size() - 1; i < j; i++, j--) {
if (values[i] != values[j]) {
return false;
}
}
return true;
}
};
Python
class Solution:
def findFirstHalfEnd(self, node):
fast = slow = node
while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
return slow
def reverseList(self, node):
previous, current = None, node
while current is not None:
nextNode = current.next
current.next = previous
previous = current
current = nextNode
return previous
def isPalindrome(self, head: ListNode) -> bool:
# 判断边界情况
if head is None:
return True
# 找到前半部分链表的为节点并反转后半部分链表
firstHalfEnd = self.findFirstHalfEnd(head)
secondHalfStart = self.reverseList(firstHalfEnd.next)
# 判断是否为回文
ans, firstPosition, secondPosition = True, head, secondHalfStart
while ans and secondPosition is not None:
if firstPosition.val != secondPosition.val:
return False
firstPosition = firstPosition.next
secondPosition = secondPosition.next
# 还原反转的链表
firstHalfEnd.next = self.reverseList(secondHalfStart)
return ans