美文网首页
算法之验证输入是否为回文(链表)

算法之验证输入是否为回文(链表)

作者: 木子小三金 | 来源:发表于2020-05-20 10:39 被阅读0次
    package list;
    
    /**
     * @ClassName PalindromeLink
     * @Description 单链表形式验证输入是否为回文
     * @Author lixin
     * @Date 2020/5/18 10:47 上午
     */
    public class PalindromeLink {
    
        /**
         * 输入链表是否为回文
         * 思路 :
         * 1、通过"快慢指针"方式 ,创建2个指针,快指针每次向下走2步,慢指针每次向下走1步,当快指针到最后一个节点时,慢指针指向的即为中间节点
         * 2、慢指针每次向后迁移一个节点后,反转走过的节点。
         * 3、找到中间指针后,创建一个新指针,指向中间节点,然后慢指针继续向下单次移动一个节点,新指针向下单次移动一个节点,对比两个节点内容,如果不相等,则不是回文 ,全部相等则为回文。
         * 4、注意链表奇偶数区别
         * @param head
         * @return
         */
        public boolean isPalindrome(Node head){
    
            Node fast = head;
            Node slow = head;
            Node next = slow.next;
    
            while(true){
                if(null == fast || null == fast.next || null == fast.next.next){
                    break;
                }
    
                /**
                 * 快指针向下走2步,这里要先移动快指针,否则慢指针批转后,会影响快指针移动
                 */
                fast = fast.next.next;
    
                /**
                 * 慢指针向下走1步,并反转经过的节点
                 * 要点:
                 * 1、需要记录3个指针:当前指针、上一节点、下一节点
                 * 2、当前指针向后移动
                 * 3、反转指向关系
                 */
                Node pre = slow; //记录上一节点
                slow = next; //当前指针向后移动
                next = slow.next; //记录下一节点
                pre.next = null; //删除上一节点的next
                slow.next = pre; //反转
            }
    
            /**
             * 如果链表长度奇偶与快指针结束关系
             * 长度奇数:fast.next == null
             * 长度偶数:fast.next != null
             *
             * 当链表长度为奇数时,跳过中间节点,从反转后的第一个节点开始比较
             */
            if(null == fast.next){
                slow = slow.next;
            }
    
            boolean palindrome = true;
            while(true){
                if(null == slow || null == next){
                    break;
                }
    
                if(slow.data != next.data){
                    palindrome = false;
                    break;
                }
    
                slow = slow.next;
                next = next.next;
            }
    
            return palindrome;
        }
    
        public static void main(String[] args) {
            ListOperator operator = new ListOperator();
            /**
             * 数组转链表,可自行实现
             */
            Node head = operator.fromArray(new Integer[]{1,2,3,3,2,1});
    
            PalindromeLink link = new PalindromeLink();
            System.out.println(link.isPalindrome(head));
        }
    }
    

    相关文章

      网友评论

          本文标题:算法之验证输入是否为回文(链表)

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