​ Please judge whether a linked list is palindrome linked list.

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

Advance: Can you use O(n) time complexity and O(1) space complexity to solve this problem?

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

Solutions:

First, find the middle node of the list, which can be solved by fast and slow pointers. The fast pointer speed is 2, and the slow pointer speed is 1. When the fast pointer traverses the list, the slow pointer just goes to the middle node (relative).

Then it is to determine whether it is a palindrome list:

If we don't consider the advanced requirements, we can do it in tens of millions of ways. The first half can be temporarily stored in a new array, linked list, hash table and other data structures, and then taken out in reverse order, compared with the values of each node in the second half of the linked list. The simpler is to directly use data structure stack, first in and then out, press the nodes into the stack, and then pop up the nodes from the stack successively after arriving at the intermediate nodes, and then compare with the node values in the second half.

Directly thinking about the advanced requirements, under the O(1) space complexity, we can only choose to operate the original linked list to complete the problem. Fortunately, this problem only requires returning Boolean values, even if the original linked list is changed, there is no need to worry. We can reverse the second half of the list, and use the iterative method to reverse the list. The time complexity is O(n), and the space complexity is O(1), so it meets the requirements. Then start to compare the value between the original chain header node and the reverse chain header node.

All kinds of detailed methods of reversing the linked list have been solved in detail in the question of the last few days. For those who haven't seen it, you can read the article: LeetCode 206: reversing linked list

Java:

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if (fast == null || fast.next == null) return true;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode newHead = reverseList(slow.next);
        while (newHead != null) {
            if (head.val != newHead.val) return false;
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }
	//Reverse linked list function -- see the previous article for details
    private ListNode reverseList(ListNode head) {
        if (head.next == null) return head;
        ListNode pre = null;
        ListNode tmp;
        while (head!= null) {
            tmp = head.next;//tmp stage the next node of the current node
            head.next = pre;//Current node next points to pre
            pre = head;//Refresh pre
            head = tmp;//Refresh the current node to tmp
        }
        return pre;
    }
}

Python:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast, slow = head, head
        if not fast or not fast.next: return True
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        newHead = self.reverseList(slow.next)
        while newHead:
            if newHead.val != head.val: return False
            newHead = newHead.next
            head = head.next
        return True

    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pre, tmp = None, None
        while (head):
            tmp = head.next
            head.next = pre
            pre = head
            head = tmp
        return pre

Welcome to study together: love to write Bug