234.Palindrome Linked List

[title]

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

[problem solving C + +]

Time complexity of O(n) and space complexity of O(1) are required. That is to say, you can't open an array to store values. Since the list cannot be traversed reversely, if you want to judge whether the palindrome is or not by comparison, you must first reverse it. Where to reverse is a problem, the midpoint is certain. But if you deal with it like the last question, which is 876, it will be a little more troublesome. In fact, the location of the midpoint can also be found through the fast and slow pointer, and 19 questions is a way of thinking. There is no need for n here, just two steps for fast pointer and one step for slow pointer.

In this way, the Follow up of this problem is quite comprehensive. It combines the link list reversal T206 + midpoint search T876 (fast and slow pointer T19).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *fast,*slow;
        fast = slow = head;
        while(fast)
        {
        	//If the next step does not exist, it means it has reached the end node 
        	if(fast->next)
        		fast = fast->next->next;
       		else fast = fast->next;
       		slow = slow->next;
        }
        //The slow here is not the midpoint, but the first node we need to reverse.
		//For example, 1,2,3,4,5 slow points to 4 
        ListNode* tmp = NULL,*re = NULL;
        //Reverse link list 
        while(slow)
        {
        	tmp = slow->next;
        	slow->next = re;
        	re = slow;
        	slow = tmp;
        }
        //Sequential comparison 
        while(re&&head)
        {
        	if(head->val!=re->val)
        		return false;
       		head = head->next;
       		re = re->next;
        }
        return true;
    }
};

[Python version of problem solving]

The idea is the same as C + +.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast = slow = head
        while fast != None:
            if fast.next is None:
                fast = fast.next
            else:
                fast = fast.next.next
            slow = slow.next
        newL = tmp = None
        while slow != None:
            tmp = slow.next
            slow.next = newL
            newL = slow
            slow = tmp
        while newL != None and head != None:
            if newL.val != head.val:
                return False
            newL = newL.next
            head = head.next
        return True