回文链表

逃离我推掉我的手 2022-11-11 05:14 164阅读 0赞

> 昨天练习了 [验证回文字符串][Link 1] ，回文的定义已经在该篇中定义过了，今天练习 [回文链表][Link 2]。

# 题目描述 #

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

示例 1:

输入: 1->2
    输出: false

示例 2:

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

## 进阶 ##

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

# 思路 #

昨天练习 [验证回文字符串][Link 3] 使用了镜像对称思维，其思想是建立在 **长度已知** 并能使用 **双指针** 基础上。

但对于链表来说，其 **长度** 是不可知的，并且凭虚生成的指针是不能指向其尾结点的，所有 **镜像对称** 想法 pass。

## 双指针——中间对称 ##

考虑到 **回文** 的目的主要是 **对称**，两端（镜像）对称已经被我们否定。那么，是否可以使用 **中点对称** 呢？

同样的，我们可以使用 **双指针——快慢指针** ，获取到链表的中间节点。

1.  当快指针遍历到尾节点时，**慢指针遍历的节点即是中间节点**
2.  将链表的后半部分进行 [反转链表][Link 4]
3.  将反转后的链表与 **原链表** 进行对比，返回结果即可

# 实现 #

/*
     * @lc app=leetcode.cn id=234 lang=javascript
     *
     * [234] 回文链表
     */
    
    // @lc code=start
    /**
     * 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) {
        if (!head.next) return true
    
    	// 获取链表中间节点
        const checkMiddle = function(fast, slow) {
            if (fast && fast.next) {
                return checkMiddle(fast.next.next, slow.next)
            } else {
                return slow
            }
        }
    	// 反转后半部分
        const reverseList = function(head) {
            let curHead = head,
                newHead = temp = null
            while (curHead) {
                temp = curHead
                curHead = curHead.next
                temp.next = newHead
                newHead = temp
            }
            return newHead
        }
        let slow = checkMiddle(head, head),
            list = reverseList(slow)
        // console.log(slow, list)
        let p1 = head,
            p2 = list,
            result = true
        while(result && p2) {
            if (p1.val === p2.val) {
                p1 = p1.next
                p2 = p2.next
            } else {
                result = false
            }
        }
        slow.next = reverseList(list) // 将后半段反转的链表恢复原状
        return result
    };
    // @lc code=end

[Link 1]: https://leetcode-cn.com/problems/valid-palindrome/
[Link 2]: https://leetcode-cn.com/problems/palindrome-linked-list/
[Link 3]: http://varlinux.com/article/detail/f59749d4-eb68-453f-a0af-8928e0535f94
[Link 4]: https://leetcode-cn.com/problems/reverse-linked-list/