LeetCode(234) determines whether a linked list is palindromic

Determine if a linked list is palindromic

Palindrome Linked List

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

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

Key skills: Empty linked list, only one node, two identical nodes are palindrome, use the fast and slow pointer to move to the middle node, and then move a node back, reverse the nodes in the latter half, and compare with the nodes in the first half, the end of the second half of the traversal shall be subject.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
    
        ListNode quick = head;
        ListNode slow = head;
        while(quick.next ! =null&& quick.next.next ! =null) {
            quick = quick.next.next;
            slow = slow.next;
        }
        
        slow = slow.next; // Note the move back one
        
        //slow performs a wave of list inversion
        ListNode preNode = null;
        ListNode current = slow;
        ListNode nextNode = null;
        while(current ! =null) {
            nextNode = current.next;
            current.next = preNode;
            preNode = current;
            current = nextNode;
        }
        while(preNode ! =null) {
            if(preNode.val ! = head.val) {return false;
            }
            preNode = preNode.next;
            head = head.next;
        }
        return true; }}Copy the code

• Time complexity: O(n)O(n), where nn refers to the size of the list.
• Space complexity: O(1)O(1), we are changing Pointers one by one, we are on the stack stack frame no more than O(1)O(1).

Another way to do it is to iterate through an array, one in front of the other, and one in front of the other, but order n space.