Title address: https://leetcode-cn.com/problems/palindrome-linked-list-lcci/

Write a function to check whether the input linked list is palindrome.

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

Advanced:

Can you solve this problem with O(n) time complexity and O(1) space complexity?

The meaning of this question is similar to that of question 9, which is to judge whether the input linked list is a palindrome, that is, the array is cut from the middle and both sides are symmetrical.

1, Blasting method

The first thing I think of is the stupidest way. First move the linked list to the array, and then traverse the array head and tail. If there is an exception, return false immediately, and return true after execution.

A small mistake was made here. I forgot to put Integer in the list. When I directly if, I used = =, resulting in an error in the use case [- 129, - 129]

The results are as follows:

26 / 26 pass test cases

Status: passed

Execution time: 4 ms

Memory consumption: 42.2 MB

public static boolean isPalindromeMe(ListNode head) {
    if (null == head) return true;
    List<Integer> list = new ArrayList<>();
    ListNode item = head;
    while (null != item) {
        list.add(item.val);
        item = item.next;
    }
    int headIndex = 0, endIndex = list.size() - 1;
    while (headIndex < endIndex) {
        if (!list.get(headIndex).equals(list.get(endIndex))) return false;
        headIndex++;
        endIndex--;
    }
    return true;
}

Of course, the result is not ideal. After all, there are advanced practices. Let's take a look at the practices of the big guys

Before looking at the official method, you should learn what the fast and slow pointer is

Speed pointer is to define two pointers, moving faster and slower, so as to create the difference you want. This difference allows us to find the corresponding node on the linked list.

The concept means that we only need to create two pointers, one fast and one slow, according to our needs, which is the fast and slow pointer

There are no special requirements for the speed of the pointer. If you want half of the linked list, the step length of the fast needle is twice that of the slow needle; If you want the penultimate in the list, the step gap between fast and slow needles is 1; To judge whether there is a ring in the linked list, you only need to use a fast needle twice as fast as a slow needle to see if it will meet.

2, Official speed pointer method

The fast and slow needle of this problem is obviously that the fast needle is twice as fast as the slow needle.

He first finds the middle position with a fast and slow needle, then reverses the second half of the linked list, and then restores the linked list after comparison.

The time here is 2ms

For the step of deleting the contrast and then reversing it, the time directly becomes 1ms, exceeding 100%

The results are as follows:

26 / 26 pass test cases

Status: passed

Execution time: 2 ms

Memory consumption: 41 MB

public boolean isPalindrome(ListNode head) {
    if (head == null) {
        return true;
    }

    // Find the tail node of the first half of the linked list and reverse the second half of the linked list
    ListNode firstHalfEnd = endOfFirstHalf(head);
    ListNode secondHalfStart = reverseList(firstHalfEnd.next);

    // Determine whether palindrome
    ListNode p1 = head;
    ListNode p2 = secondHalfStart;
    boolean result = true;
    while (result && p2 != null) {
        if (p1.val != p2.val) {
            result = false;
        }
        p1 = p1.next;
        p2 = p2.next;
    }

    // Restore linked list and return results
    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

private ListNode endOfFirstHalf(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

The idea of the official answer is good. Restore it to others after use to avoid problems in subsequent use. However, most people don't talk about martial ethics when brushing leetcode. Just solve their own things. After all, this is an algorithm, not a job.

Today, I learned the usage of fast and slow needles. It's not a loss. After all, I heard about fast and slow needles every day. Today, I've seen it.