LeetCode Notes_#234_回文链表

LeetCode Notes_#234_回文链表

Contents

题目

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2
输出: false

示例 2:

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

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

解答

方法1:用ArrayList保存数据并判断

class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        //用ArrayList保存所有值
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        int left = 0;
        int right = list.size() - 1;
        while(left < right){
            if(!list.get(left).equals(list.get(right)))
                return false;
            left++;
            right--;
        }
        return true;
    }
}

复杂度分析

时间复杂度:O(n)
空间复杂度:O(n)

方法2:双指针+反转链表

回文串应该是对称的,所以我们想办法找到中间的节点,然后比较前后两个半段是否是对称的。
首先利用双指针法,找到链表最中间的节点(也就是前半段的最后一个节点),就可以划分出前半段,后半段。(对于size是奇数的链表,中间的数字算在前半段中,比较的时候也无需比较)
然后将后半段反转,逐个比较前后半段的每个节点是否相同,如果都相同,说明是对称的,是回文串。否则,不是回文串。
需要注意的是,这样的写法会改变输入的head链表结构,返回结果之前需要恢复链表结构。

class Solution {
    public boolean isPalindrome(ListNode head) {
        //空链表
        if(head == null) return true;
        //找到前半段的最后一个节点
        ListNode EndOfFirstHalf = findMid(head);
        //反转后半段链表
        ListNode ReversedSecondHalf = reverse(EndOfFirstHalf.next);
        //比较前半段和反转后的后半段(回文串应该是对称的)
        //对于size是奇数的链表,无需比较中间的数字
        ListNode p1 = head;
        ListNode p2 = ReversedSecondHalf;
        boolean result = true;
        while(result && p2 != null){
            if(p1.val != p2.val) result = false;
            p1 = p1.next;
            p2 = p2.next;
        }
        //返回结果之前,需要还原输入的链表
        EndOfFirstHalf.next = reverse(ReversedSecondHalf);
        return result;
    }
    //反转链表
    private ListNode reverse(ListNode head){
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode cur = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
    //双指针法找到前半部分的最后一个节点
    //如果链表size为奇数,中间节点算在前半部分
    private ListNode findMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        //判断条件需要画一下草稿来确定
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

复杂度分析

时间复杂度:O(n)
空间复杂度:O(1)

原文地址:https://www.cnblogs.com/Howfars/p/13537093.html