判断链表是否为回文链表的三种方法 | 算法详解

判断一个链表是否为回文链表是一个常见的算法问题。回文链表是指链表中的元素顺序和逆序相同。我们可以通过以下几种方法来实现这个判断：

方法一：使用栈

1. 遍历链表并将元素压入栈中：首先遍历链表，将每个节点的值压入栈中。
2. 再次遍历链表并与栈顶元素比较：再次遍历链表，每次从栈中弹出一个元素并与当前节点的值进行比较。如果所有元素都匹配，则链表是回文链表。

function isPalindrome(head) {
    let stack = [];
    let current = head;
    
    // 将链表元素压入栈中
    while (current !== null) {
        stack.push(current.val);
        current = current.next;
    }
    
    // 再次遍历链表并与栈顶元素比较
    current = head;
    while (current !== null) {
        if (current.val !== stack.pop()) {
            return false;
        }
        current = current.next;
    }
    
    return true;
}

方法二：快慢指针

1. 找到链表的中间节点：使用快慢指针找到链表的中间节点。
2. 反转后半部分链表：将链表的后半部分反转。
3. 比较前后两部分链表：比较前半部分和反转后的后半部分链表，如果所有节点都匹配，则链表是回文链表。

function isPalindrome(head) {
    if (head === null || head.next === null) {
        return true;
    }
    
    let slow = head;
    let fast = head;
    
    // 找到中间节点
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 反转后半部分链表
    let prev = null;
    let current = slow;
    while (current !== null) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    // 比较前后两部分链表
    let p1 = head;
    let p2 = prev;
    while (p2 !== null) {
        if (p1.val !== p2.val) {
            return false;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    
    return true;
}

方法三：递归

1. 递归遍历链表：使用递归遍历链表，并在递归返回时比较节点值。
2. 比较节点值：在递归返回时，比较当前节点值与递归返回的节点值是否相同。

function isPalindrome(head) {
    let frontPointer = head;
    
    function recursivelyCheck(currentNode) {
        if (currentNode !== null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val !== frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }
    
    return recursivelyCheck(head);
}

总结

• 方法一：使用栈的方法简单直观，但需要额外的空间来存储链表元素。
• 方法二：快慢指针的方法在空间复杂度上更优，但需要修改链表结构（反转后半部分链表）。
• 方法三：递归的方法简洁，但可能会因为递归深度过大而导致栈溢出。

根据具体场景和需求，可以选择合适的方法来判断链表是否为回文链表。