LeetCode 234:回文链表 Palindrome Linked List-阿里云开发者社区

开发者社区> 开发与运维> 正文

LeetCode 234:回文链表 Palindrome Linked List

简介: ​请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? Follow up:Could you do it in O(n) time and O(1) space? 解题思路: 首先是寻找链表中间节点,这个可以用快慢指针来解决,快指针速度为2,慢指针速度为1,快指针遍历完链表时,慢指针刚好走到中间节点(相对)。


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

Given a singly linked list, determine if it is a palindrome.

示例 1:

输入: 1->2
输出: false

示例 2:

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

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

Follow up:
Could you do it in O(n) time and O(1) space?

解题思路:

首先是寻找链表中间节点,这个可以用快慢指针来解决,快指针速度为2,慢指针速度为1,快指针遍历完链表时,慢指针刚好走到中间节点(相对)。

然后是判断是否是回文链表:

不考虑进阶要求的话,方法千千万。可以把前半部分暂存入新的数组、链表、哈希表等等数据结构,然后依次倒序取出,与后半部分链表每个节点的值对比即可。更简单的是直接用数据结构 - 栈,先进后出,把节点压入栈中,到中间节点后,依次从栈中弹出节点,与后半部分的节点值对比即可。

直接思考进阶要求,在 O(1) 的空间复杂度下,只能选择操作原链表来完成该题。好在这道题只要求返回布尔值,即便把原链表改变了也不用担心。我们可以将链表后半部分 反转,利用迭代法反转链表,时间复杂度为 O(n),空间复杂度为 O(1),所以符合要求。然后从原链表头节点 与 反转后后半部分链表头节点开始对比值即可。

反转链表的各种详细方法在前几日的那道题中已经详细解答过,未看过的朋友可以先看那一篇:LeetCode 206:反转链表 Reverse Linked List

Java:

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if (fast == null || fast.next == null) return true;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode newHead = reverseList(slow.next);
        while (newHead != null) {
            if (head.val != newHead.val) return false;
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }
    //反转链表函数--详情请看前文
    private ListNode reverseList(ListNode head) {
        if (head.next == null) return head;
        ListNode pre = null;
        ListNode tmp;
        while (head!= null) {
            tmp = head.next;//tmp暂存当前节点的下一个节点
            head.next = pre;//当前节点下一个指向pre
            pre = head;//刷新pre
            head = tmp;//刷新当前节点为tmp
        }
        return pre;
    }
}

Python:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast, slow = head, head
        if not fast or not fast.next: return True
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        newHead = self.reverseList(slow.next)
        while newHead:
            if newHead.val != head.val: return False
            newHead = newHead.next
            head = head.next
        return True

    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pre, tmp = None, None
        while (head):
            tmp = head.next
            head.next = pre
            pre = head
            head = tmp
        return pre

欢迎关注公.众号一起学习: 爱写Bug

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章