This is [027, palindrome linked list] on LeetCode. The difficulty is [simple]

subject

Given the head node of a linked list, please judge whether it is a palindrome linked list.

If a linked list is a palindrome, the sequence of linked list nodes is the same from front to back and from back to front.

Example 1

input: head = [1,2,3,3,2,1]
output: true

Example 2:

input: head = [1,2]
output: false

Problem solving (speed pointer, reverse)

Train of thought analysis

A characteristic of palindrome linked list is symmetry, that is, the value of the first node of the linked list is equal to the value of the last node, and so on. Therefore, we can divide the linked list into two linked lists from the middle, then reverse the previous linked list or the next linked list, and finally traverse the two linked lists at the same time. In the process of traversal, compare the values of the two nodes. If they are not equal, it is not a palindrome linked list, otherwise it is a palindrome linked list

It should be noted that the meaning of the question only allows us to judge whether the linked list is a palindrome linked list, so we can't change the structure of the original linked list. Reversing the linked list requires that the next node of the tail node is null, that is, we can't reverse the previous linked list (the previous linked list needs to be disconnected, that is, the tail node needs to point to null), Only the last linked list can be reversed (its tail node points to null). Generally speaking, it is logically divided into two linked lists and does not disconnect the linked list in the physical structure

step

Step 1 (divide the linked list into two linked lists from the middle in logical structure)

If you want to divide the logical structure into two linked lists from the middle, you need to find the head node of the latter linked list. The following is divided into two cases

• When the length of the linked list is even, the linked list is symmetrical about the middle chain and needs to be disconnected from the middle chain (logical structure, actual continuous opening). Therefore, it is necessary to find the tail node of the previous linked list, and the next node of the tail node is the head node of the later linked list
• When the length of the linked list is odd, the linked list is symmetrical about the intermediate node and needs to be disconnected from the left and right chains of the intermediate node (the intermediate node is common, so there is no need to compare). Therefore, it is necessary to find the intermediate node of the linked list, and the next node of the intermediate node is the head node of the later link

To sum up, we can use the fast and slow pointer to find the middle node of the linked list. When the linked list is even, we need to find the tail node of the previous linked list, so the logic (loop termination condition) will be slightly different from finding the middle node

Step 2 (reverse the last linked list)

Reverse linked list

Step 3 (traverse the two linked lists at the same time and compare the node values)

Step 4 (reverse the last linked list again to restore the original structure)

code implementation

public class Solution {
   
    public boolean isPalindrome(ListNode head) {
       /* When the linked list is even, the tail node of the previous linked list is returned, and the next node of the tail node is the head node of the next linked list
        *  When the linked list is odd, the intermediate node of the linked list is returned, and the next node of the intermediate node is the head node of the subsequent linked list*/
        ListNode firstHalfEndOrMiddleNode = EndOrMiddleNode(head);
        // Returns the head node of the next linked list
        ListNode secondHalfHead = firstHalfEndOrMiddleNode.next;
        Boolean aBoolean = equals(head, reverseList(secondHalfHead));
        // Restore the original structure
        reverseList(secondHalfHead);
        return aBoolean;
    }

    public ListNode EndOrMiddleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        /* When the length of the linked list is even, the termination condition is that fast terminates at the penultimate node of the linked list, that is, its lower node is null
        * At this time, slow is at the tail node of the previous linked list
        * When the length of the linked list is odd, the termination condition is that fast terminates at the tail node of the linked list, that is, its next node is null
        * At this time, slow is in the middle node of the linked list*/
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    public ListNode reverseList(ListNode head) {
        ListNode currNode = head;
        ListNode preNode = null;
        while (currNode != null) {
            ListNode nextNode = currNode.next;
            currNode.next = preNode;
            preNode = currNode;
            currNode = nextNode;
        }
        return preNode;
    }

    public Boolean equals(ListNode head1, ListNode head2) {
        while (head2 != null) {
            if (head1.val != head2.val) {
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return true;
    }
}

Complexity analysis

Suppose l the length of the linked list is n

Time complexity:

At first, the linked list needs to be traversed and divided into two parts, with a time complexity of O(n). When the linked list is reversed, the time complexity is O(n/2). Finally, when the two linked lists are traversed at the same time, the time complexity is O(n/2), so the total time complexity is O(n) + 2O(n/2) = O(n)

Space complexity:

Only a few fixed nodes are declared, so the space complexity is O(n)