Leetcode刷题(第234题)——回文链表

x33g5p2x  于2022-03-17 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(324)

一、题目

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题

二、示例

输入:head = [1,2,2,1]
输出:true

输入:head = [1,2]
输出:false

三、思路
本题采用快慢指针的思路,找到中间位置的节点然后进行断开,将后半部分的链表的顺序倒过来,然后进行while循环比对。
四、代码展示

/**
 * 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 slow = head
    let fast = head.next
    while(slow && fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    let p1 = slow.next
    slow.next = null
    let p2 = null
    while(p1) {
        let temp = p1.next
        p1.next = p2
        p2 = p1
        p1 = temp
    }
    let p3 = head
    while(p2 && p3) {
        if(p2.val !== p3.val) {
            return false
        }
        p2 = p2.next
        p3 = p3.next
    }
    return true
};

五、总结

相关文章