Leetcode algorithm refers to offer II 027 Palindrome linked list

Topic link ： The finger of the sword Offer II 027. Palindrome list

Ideas

Algorithm ： Double pointer
data structure ： Linked list
Ideas ： First, turn the second half of the list over , Then use two pointers to traverse from the beginning and from the middle to determine whether they are the same , If it is the same, it is a palindrome linked list , Otherwise, it's not a palindrome linked list , But whether it is a palindrome linked list or not , The flipped linked list still needs to be flipped back .
1. Use the speed pointer , Quick pointer quick Two steps at a time , Slow pointer slow One step at a time , When the pointer comes to the end , The slow pointer is right in the middle of the linked list ;（ If the length of the list is odd , The fast pointer finally goes to the last element , If the length of the list is even , The fast pointer finally goes to the penultimate element ）
2. Start from the middle of the linked list , Flip the following nodes one by one , That is, the current node originally points to the next node , Change to point to the previous node ;
3. Double pointers start from the beginning and end of the linked list respectively , Traverse to determine whether the current node values are equal , End when the two pointers finally meet ;
4. Start from the middle of the linked list , Then flip the following nodes back .

Code

C++

class Solution {
    
public:
    bool isPalindrome(ListNode* head) {
    
        if (head == nullptr || head->next == nullptr) {
    
            return true;
        }
        // 1. The speed pointer finds the middle position of the linked list 
        ListNode *quick = head, *slow = head;
        while (quick->next != nullptr && quick->next->next != nullptr) {
    
            slow = slow->next;
            quick = quick->next->next;
        }
        // 2. Flip the subsequent nodes from the middle of the linked list 
        ListNode *cur = slow->next;
        slow->next = nullptr;
        while (cur != nullptr) {
    
            ListNode *nxt = cur->next;
            cur->next = slow;
            slow = cur;
            cur = nxt;
        }
        // 3. Double pointers traverse from the beginning to the end 
        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. Flip the flipped node back 
        cur = tail->next;
        tail->next = nullptr;
        while (cur != nullptr) {
    
            ListNode *nxt = cur->next;
            cur->next = tail;
            tail = cur;
            cur = nxt;
        }
        return res;
    }
};

Of course , If you find double pointers troublesome , You can also traverse the linked list, save it to the array, and then determine whether it is a palindrome .

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:
        #  Judge the boundary 
        if head is None:
            return True

        #  Find the node of the first half of the linked list and reverse the second half of the linked list 
        firstHalfEnd = self.findFirstHalfEnd(head)
        secondHalfStart = self.reverseList(firstHalfEnd.next)

        #  Judge whether it is palindrome 
        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

        #  Restore inverted linked list 
        firstHalfEnd.next = self.reverseList(secondHalfStart)

        return ans