【LeetCode 234】回文链表

今天药忘吃喽~ 2022-11-28 00:50 158阅读 0赞

#### 题目描述 ####

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
    输出: false

示例 2:

输入: 1->2->2->1
    输出: true

进阶：  
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

#### 解题思路 ####

**字符串拼接：**

对于这道题，最直接的思路就是，遍历链表，同时正向和反向拼接链表的节点，最后比较两个拼接出来的字符串是否一样。

这种方式的时间复杂度为O(n)，空间复杂度为O(1)

**递归遍历：**

*  首先，定义一个全局的指针pointer，其初始值为head，用来正序遍历
 *  然后，调用递归函数，对链表进行逆序遍历，当头部节点为null的时候停止遍历
 *  如果正序遍历的节点值和逆序遍历的节点值都相等，就返回true，否则就返回false

这种方式的时间复杂度为O(n)，空间复杂度为O(1)

#### 代码实现 ####

**字符串拼接：**

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {boolean} */
    var isPalindrome = function(head) { 
        let a = ""
        let b = ""
        while(head){ 
            const nodeVal = head.val
            a = a + nodeVal
            b = nodeVal + b
            head = head.next
        }
        return a === b
    };

**递归遍历：**

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {boolean} */
    
    
    let pointer
    function fn(head) { 
        if(!head) return true
        const res = fn(head.next) && (pointer.val === head.val)
    
        pointer = pointer.next
        return res
    } 
    
    var isPalindrome = function(head) { 
        pointer = head
        return fn(head)
    };

#### 提交结果 ####

**字符串拼接：**  
![在这里插入图片描述][20200816184949125.png]  
**递归遍历：**

![在这里插入图片描述][20200816185851965.png]

[20200816184949125.png]: /images/20221124/96580f249dce43579e260933fd04625b.png?
[20200816185851965.png]: /images/20221124/c32956b4f80e4934968ec640ea2f83ed.png?