This is the 12th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

First, understand the topic

Attached is a link to the original title: 234. Palindrome linked list

Give you a single linked list of the head node head, please determine whether the list is a palindrome list. If so, return true; Otherwise, return false.

Example 1:

Input: head = [1,2,2,1] output: trueCopy the code

Example 2:

Input: head = [1,2] output: falseCopy the code

Ii. Solution analysis

1. Thinking about reducing space complexity

When we do problems, we usually try to reduce the time and space complexity as much as possible. For reducing space complexity, there are mainly the following considerations:

  • We should try to avoid using themO(n)The usual way to do that isChange the input;
  • Therefore, we can reverse the second half of the list (modify the structure of the list) and compare the first half with the second half;
  • After the comparison is complete, we should restore the linked list as it was;
  • Although test cases can pass without recovery, people who use this function usually don’t want the list structure changed;
  • This method can reduce the space complexityO(1)However, in concurrent environment, this method also has disadvantages;
  • In a concurrent environment, the function needs to lock access to the list from other threads or processes while it is running, because the list can be modified during the execution of the function.

2. Steps to solve the problem

According to the above description and the analysis of complexity. The whole process can be divided into the following five steps:

  • Find the end of the first half of the list;
  • Reverse the second half of the list;
  • Judge whether palindrome;
  • Restore linked list;
  • Returns the result.

Three, code implementation

Based on the above solution, we will use JS to implement this problem. The specific implementation code is as follows:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {boolean}* /
​
// Flip the linked list
const reverseList = (head) = > {
    let prev = null;
    let curr = head;
    while(curr ! = =null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}
​
// Find the end of the first half
const endOfFirstHalf = (head) = > {
    let fast = head;
    let slow = head;
    while(fast.next ! = =null&& fast.next.next ! = =null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
​
var isPalindrome = function(head) {
    // 1. Check whether the list is empty. If it is empty, return true
    if (head == null) return true;
​
    // 2. Find the last node of the first half of the list and reverse the last half of the list
    const firstHalfEnd = endOfFirstHalf(head);
    const secondHalfStart = reverseList(firstHalfEnd.next);
​
    // 3. Check whether it is a palindrome
    let p1 = head;
    let p2 = secondHalfStart;
    let result = true;
    while(result && p2 ! =null) {
        if(p1.val ! = p2.val) result =false;
        p1 = p1.next;
        p2 = p2.next;
    }        
​
    // 4. Restore the list and return the result
    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
};
Copy the code

Fourth, complexity analysis

Time complexity: O(n), where n refers to the size of the list.

Space complexity: O(1). We only change the direction of the nodes in the original list, and the stack frame on the stack is no more than O(1).

Palindrome linked list

The above is about the palindrome linked list of questions, do not know whether it is helpful to small friends?

We’ll see you next time at 👋👋👋