当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.234.Palindrome Linked List 判断是否回文单链表

LeetCode.234.Palindrome Linked List 判断是否回文单链表

题目描述

234 Palindrome Linked List
https://leetcode-cn.com/problems/palindrome-linked-list/

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

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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


解题过程

判断是否回文单链表

递归反向遍历

判断是否回文就需要正向遍历和反向遍历后比较,由于题目不让用额外空间,所以无法把链表反转后存储到一个新链表中。
由于 递归遍历可以实现从后往前的倒序访问,就想到递归反向遍历的同时,维护一个全局正向遍历的指针,每次递归访问结点时和正向指针比较。
注意,虽然递归写法中只维护了一个正向遍历指针,但空间复杂度并不是 O(1),因为递归要用到一个大小为n的栈,所以空间复杂度还是 O(n),并不是最优解。
虽然递归方法不是最优解,但思想很值得学习,是一个技巧性很强的解法。
时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV2020 {
    // 全局正向遍历指针
    private ListNode cur;
    public boolean isPalindrome(ListNode head) {
        if (null == head || null == head.next) {
            return true;
        }
        cur = head;
        return isPalindromeRecursive(head);
    }

    // 递归倒序遍历head,同时和全局正向遍历指针cur比较,返回是否相等
    private boolean isPalindromeRecursive(ListNode head) {
        if (null == head) {
           return true;
        }
        boolean isPalindrome = isPalindromeRecursive(head.next) && (head.val == cur.val);
        cur = cur.next;
        return isPalindrome;
    }
}

双指针找中点反转后半段

我的第一个思路就是用 2倍速双指针,fast一次走2步,slow一次1步,找到链表中间点,然后反转链表后半段,再比较从头开始遍历和从中间点开始遍历的结果,但写起来感觉挺麻烦的,而且有些边界要处理。
没想到看题解后发现这个才是最优解。
时间复杂度 O(n),空间复杂度 O(1)


GitHub代码

algorithms/leetcode/leetcode/_234_PalindromeLinkedList.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_234_PalindromeLinkedList.java


上一篇 LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素

下一篇 LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数

阅读
评论
533
阅读预计2分钟
创建日期 2020-02-21
修改日期 2020-02-21
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论