美文网首页算法
面试题 02.06. 回文链表

面试题 02.06. 回文链表

作者: crazyfox | 来源:发表于2021-09-17 09:57 被阅读0次

    面试题 02.06. 回文链表

    难度简单78

    编写一个函数,检查输入的链表是否是回文的。

    示例 1:
    输入: 1->2
    输出: false

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

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

    class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) return true;
            if(head.next.next == null) return head.val == head.next.val;
    
            ListNode mid = middleNode(head);
            ListNode rHead = reverse(mid.next);
            ListNode lHead = head;
    
            while(rHead!=null){
                if(lHead.val != rHead.val) return false;
                rHead = rHead.next;
                lHead = lHead.next;
            }
            return true;
        }
    
        public ListNode middleNode(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;
    
        }
        public ListNode reverse(ListNode head){
    
                ListNode newHead = null;
                while(head !=null){
                    ListNode tmp = head.next;
                    head.next = newHead;
                    newHead=head;
                    head=tmp;
                }
                return newHead;
        }
    }   
    

    相关文章

      网友评论

        本文标题:面试题 02.06. 回文链表

        本文链接:https://www.haomeiwen.com/subject/tmvfgltx.html