LeetCode 234. 回文链表

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 234. 回文链表原题链接简单

作者：

小呆呆 , 2020-09-05 10:58:33 , 所有人可见 , 阅读 856

8

1

题目描述

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

样例

输入: 1->2
输出: false

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

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

算法分析

核心思路：找到链表右半部分链，并将右半部分链进行反转，对左半部分链表和反转后的右半部分链表的元素进行一一比较，若都相同则是回文链表

具体方法

1、通过快慢指针slow和fast，slow每次走一步，fast每次走两步，找到右半部分链，由于不知道链表的元素个数是奇数个还是偶数个，因此统一规则让右半部分链比左半部分链的元素个数最多多1个，初始化slow = head，fast = head.next，则slow.next就是右半部分链的开头
2、将右半部分链进行反转，由于题目要求空间复杂度是 $O(1)$ ，因此只能用迭代的方式对链表进行反转，反转后记得将 slow.next 指向null，让左右链表隔离开
3、假设左边链表的个数是x个，右边链表的个数可能是x个，也可能是x + 1个，因此比较x次，若x次中链表的元素都一一对应则是回文链表，否则不是回文链表

时间复杂度 $O(n)$

空间复杂度 $O(1)$

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    static ListNode reverse(ListNode head)
    {
        ListNode a = head,b = head.next;
        while(b != null)
        {
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        head.next = null;
        return a;
    }
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode slow = head, fast = head.next;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        //将右半部分的链表slow.next进行反转
        ListNode right = reverse(slow.next);
        ListNode left = head;
        slow.next = null;

        while(left != null && right != null)
        {
            if(left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }
}

3 评论

希望一切顺利 2020-10-23 10:33

class Solution {
    public boolean isPalindrome(ListNode head) {
        int n = 0;
        for(ListNode p = head; p != null; p = p.next) n++; //n个点
        if(n <= 1) return true;
        int half = n / 2; //想一下奇数个和偶数个的情况
        // if(n % 2 == 0) int half = n / 2 + 1;
        // else int half = n / 2;
        ListNode a = head; //head的next不变的
        for(int i = 0; i < n - half; i++) a = a.next;
        ListNode b = a.next;
        //结束时b == null
        for(int i = 0; i < half - 1; i++){
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        // while(b != null){
        //     ListNode c = b.next;
        //     b.next = a;
        //     a = b;
        //     b = c;
        // }
        ListNode p = head;
        ListNode q = a; //a的next其实还是没变的，因为是q.next也没变只是在往前走
        boolean success = true;
        for(int i = 0; i < half; i++){
            if(p.val != q.val){
                success = false;
                break;
            }
            p = p.next;
            q = q.next;
        }
        ListNode tail = a; //a的next那一段都没变，a还是指向了最后一个节点
        ListNode tmp = a.next;
        //tail指向的节点一直都是最后一个，因为是虽然说a = tmp但tmp是a.next
        //tail = a指向的这个节点的next并没有被动过
        //tail.next = null;
        //将链表恢复原状
        //System.out.println(tail.val);
        for(int i = 0; i < half - 1; i++){
            ListNode c = tmp.next;
            tmp.next = a;
            a = tmp;
            tmp = c;
        }
        //相当于把a赋给了tail暂存了一个节点的
        //tail不会跟着a往前走吗？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
        tail.next = null;
        //System.out.println(tail.val);
        return success;
}