Original address: juejin.cn/post/688705… Original address: leetcode-cn.com/problems/pa…

Topic describes

Determine if a linked list is palindromic.

Example 1:

Input: 1->2 Output: falseCopy the code

Example 2:

Input: 1->2->2->1 Output: trueCopy the code

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

Their thinking

If you think about a point, if you want to solve it in order of O(1)O(1)O(1) time, you want to solve the problem with the linked list itself. Think through this, the following train of thought can naturally come out 👇

  1. Cut a list into two symmetric lists
    • Gets the middle node of the list and its number of nodes
    • If the number of nodes is odd, the intermediate nodes can be dropped and split, otherwise the intermediate nodes are allocated to the left list
  2. Reverse one of the linked lists
  3. Compare the values of two linked lists

code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {boolean}* /
const isPalindrome = function(head) {

    /** ** splits the linked list *@param head {ListNode}
     * @return {ListNode}* /
    const splitLinkList = (head) = > {
        let prev = null
        let low = head
        let fast = low.next
        let nextHead = null
        let cnt = 1
        while (fast && fast.next) {
            prev = low
            low = low.next
            fast = fast.next.next
            cnt++
        }
        cnt = cnt * 2 - (fast ? 0 : 1)
        nextHead = low.next
        low.next = null
        if (cnt % 2= = =1) {
            prev.next = null
        }
        return nextHead
    }

    /** * reverse linked list *@param head {ListNode}
     * @return {void}* /
    const reverseLinkList = (head) = > {
        if(! head) {return null
        }
        let prev = head
        let next = head.next
        while (next) {
            head.next = next.next
            next.next = prev
            prev = next
            next = head.next
        }
        return prev
    }

    /** * check if the linked list is the same *@param head {ListNode}
     * @param nextHead {ListNode}
     * @return {boolean}* /
    const checkLinkList = (head, nextHead) = > {
        if(! head && ! nextHead) {return true
        }
        if(! head || ! nextHead || head.val ! == nextHead.val) {return false
        }
        return checkLinkList(head.next, nextHead.next)
    }

    if(! head || ! head.next) {return true
    }
    const nextHead = splitList(head)
    head = reverseLinkList(head)
    return checkLinkList(head, nextHead)
};
Copy the code