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

2020-05-20  本文已影响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));
    }
}
上一篇下一篇

猜你喜欢

热点阅读