LeetCode palindrome list of Primary Algorithms – JavaScript

The title

Title link: leetcode-cn.com/leetbook/re…

Answer key

1. Use arrays

We can use an array to store all the values of the linked list, and then use a double pointer to verify whether it is a palindrome array.

/** * 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}* /
var isPalindrome = function(head) {

    let temp = head;
    let arr = [];
    let front = 0,
        rear = 0;

    while(temp ! =null) {

        arr.push(temp.val);
        
        temp = temp.next;
    }

    rear = arr.length - 1;

    while(rear >= front) {

        if(arr[rear] ^ arr[front]) { 
            return false;
        }
        rear--;
        front++;
        
    }

    return true;

};
Copy the code

2, first get the length of the list, and then recurse

Auxiliary array is convenient, but its space complexity also reaches O (n), then do not use auxiliary array, directly to the linked list operation;

/** * 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}* /
var isPalindrome = function(head) {

    let len = 0,
        half = 0;
    let temp = head;
    
    let flag = false;
    let isodd = false;

    // Find the length of the list
    while(temp) {

        len++;
        temp = temp.next;
    }

    half = Math.ceil(len/2); 

    if(len%2= = =1) {
        isodd = true;
    }
		// a recursive function
    function compare(head,half) { // The recursive function here uses global variables. Reuse the recursive function elsewhere

        if(half === 0) {

            return head;
        }

        const h = compare(head.next,half - 1);

        if(half === 1 && isodd) { // check whether the list isodd by using the global variable isodd
            return h;
        }

        if(head.val ! == h.val) { flag =true; // Use the global flag variable to indicate whether elements at symmetric positions in the list are not equal during recursion
        }
       

        return h.next;

    }

    compare(head,half); 

    if(flag) {
        return false;
    }
    
    return true;

};
Copy the code

The recursive function in the above code cannot be reused elsewhere because it uses global variables. Here is a recursion function that can be reused (by passing objects to the recursion function).

/** * 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}* /
var isPalindrome = function(head) {

    let len = 0,
        half = 0;
    let temp = head;

    let flag = {flag:false};
    let isodd = false;

    // Find the length of the list
    while(temp) {

        len++;
        temp = temp.next;
    }

    half = Math.ceil(len/2); 

    if(len%2= = =1) {
        isodd = true;
    }


    // a recursive function
    function compare(head,half,isodd,flag) { // Change the format to reusable ~, change the flag to object pass in;

        if(half === 0) {

            return head;
        }

        const h = compare(head.next,half - 1,isodd,flag);

        if(half === 1 && isodd) { // check whether the list isodd by using the global variable isodd
            return h;
        }

        if(head.val ! == h.val) { flag.flag =true; // Use the global flag variable to indicate whether elements at symmetric positions in the list are not equal during recursion
        }
       

        return h.next;

    }

    compare(head,half,isodd,flag);  

    if(flag.flag) {
        return false;
    }
    
    return true;

};
Copy the code

N times of full comparison

The recursion used by the above two recursive algorithms is only the comparison between the first half and the second half of the list, and the number of comparisons is n/2. Therefore, complex boundary conditions need to be considered, that is, to find the middle position, and to start the comparison in the middle position;

The first half of a list is symmetric with the second half, that’s the definition of a palindrome list; A list reversed is equal to the original list, which is the definition of a palindrome list;

So you can write an algorithm that compares n times, which is easier to write than an algorithm that compares n over 2 times;

/** * 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}* /
var isPalindrome = function(head) {

    
    let temp = head;
    let flag = false;

    function compare(head,temp) {

        if(head === null) {return temp;
        }

        const t = compare(head.next,temp);

        if(t.val ! == head.val) { flag =true;
        }

        return t.next;

    }


    compare(head,temp);

    if(flag) {
        return false;
    }
    return true;
};

Copy the code

If you have a better way of thinking and reconciliation, welcome to discuss ah ~

This is a summary and implementation of each problem in LeetCode’s “Elementary Algorithms” using JavaScript. The summary is here:

Juejin. Cn/post / 700669…