234. 回文链表

发表于   |   分类于 LeetCode   |   本文已被浏览 572 次   |   暂无评论

描述

请判断一个链表是否为回文链表。
进阶
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路

解答出本体不难，问题在于进阶的时间和空间复杂的限制。想了半天还是没能想出来。

非进阶解法代码如下：

class Solution {
    public boolean isPalindrome(ListNode head) {
        LinkedList<Integer> list = new LinkedList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        Integer[] arr = list.toArray(new Integer[list.size()]);
        boolean flag = true;
        for (int i = 0; i < arr.length; i++) {
            if (!arr[i].equals(arr[arr.length - 1 - i]) ) {
                flag = false;
                break;
            }
        }
        return flag;

    }
}

运行结果：

10:41    info
                        解答成功:
                        执行耗时:16 ms,击败了9.21% 的Java用户
                        内存消耗:53 MB,击败了5.05% 的Java用户

惨不忍睹。。。

题解

给出进阶解法

快慢指针

避免使用 O(n)O(n) 额外空间的方法就是改变输入。
我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到 O(1)O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

整个流程可以分为以下五个步骤：

  1. 找到前半部分链表的尾节点。
  2. 反转后半部分链表。
  3. 判断是否回文。
  4. 恢复链表。
  5. 返回结果。
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(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;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

小结

💪加油！

添加新评论