LeetCode Algorithm 面试题 02.06. 回文链表

题目链接：面试题 02.06. 回文链表

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