Java笔记 ·

单链表回文判断

判断一个单链表是否为回文链表目前有两种实现思路。一种是通过数组记录前半部分与后半部分依次比较,一种是找到链表中间结点,将左半部分反转与右半部分依次比较,下面详细介绍。

基于数组

用数组存储链表前半段的值,使用快慢指针法来进行截取。

public boolean isPalindromeByArray(Node node){
        if (node == null) return false;
        Node fast = node;
        Node slow = node;
        if (node.next == null) return true;

        /**
         * 找到中间结点,同时用数组逆插左侧元素并保存。
         *  nodeList.add(0, slow.data); 在指定位置插入元素,原位置及之后的依次向右移动一位。
         */
        List<Integer> nodeList = new ArrayList<Integer>();
        nodeList.add(0, slow.data);
        while (fast.next != null && fast.next.next != null ) {

            fast = fast.next.next;
            slow = slow.next;
            nodeList.add(0, slow.data);
        }


        if (fast.next != null){
            // fast.next不为空,数据为偶数。
            slow = slow.next;
        }
        Node curr = slow;
        int i = 0;
        while (null != curr){
            if (curr.data != nodeList.get(i)){
                return false;
            }
            curr = curr.next;
            i++;
        }
        return true;
    }

nodeList.add(0, slow.data);插入是比较耗时的,毕竟每次插入都需要将之前的依次向右移动一位。所以可以考虑用栈实现。

基于栈的回文判断

思路同基于数组的,但因为免去了保存新结点的右移操作,所以比使用数组保存左侧数据的方式高效一些。

/**
     * 基于栈比较是否为回文--半栈
     * @param node
     * @return
     */
    public boolean isPalindromeByStack(Node node){
        if (node == null) return false;
        Node fast = node;
        Node slow = node;
        if (node.next == null) return true;

        /**
         * 找到中间结点,同时用栈保存左侧数据。
         *  
         */
        Stack<Integer> nodeList = new Stack<Integer>();
        nodeList.push(slow.data); // 1 2 3
        while (fast.next != null && fast.next.next != null ) {

            fast = fast.next.next;
            slow = slow.next;
            nodeList.push(slow.data); // 1 2 3
        }


        if (fast.next != null){
            // fast.next不为空,数据为偶数。
            slow = slow.next;
        }
        Node curr = slow;
        int i = 0;
        while (null != curr){
            if (curr.data != nodeList.pop()){
                return false;
            }
            curr = curr.next;
            i++;
        }
        return true;
    }

基于链表反转的回文判断

该方案的思路是:通过快慢指针获取中间结点,反转中间结点左侧部分,遍历并对比反转后左右两侧结点的数据判是否为回文。

只需要固定的若干个临时变量,不需要额外开辟空间

时间复杂度为O(n),空间复杂度为O(1)

该方式可以略作简化将反转左侧部分在查中间结点时同时完成。这里为了方便阅读,分开了查找中间结点和反转左侧结点的步骤,不再实现该优化。

    /**
     * 不含逻辑头节点的回文链表判断
     * 思路:
     * 遍历一遍链表,得到链表长度n,根据长度的奇偶,找到中间节点,将左半边的链表反转,然后从中间节点分两个方向向左右两边遍历,是否是回文;
     * 
     * 对左半部分链表进行反转,还原为最初的链表(目前函数未实现左半部分链表还原)
     * 
     * 
     * 1 2 3 4 5 8 9 slow 4 fast 9
     * 1 2 3 4 5 8  slow  3 fast 5
     * @return
     */
    public  boolean isPalindrome(Node head){
        if (head == null) return false;
        PrintUtill.println("开始执行找到中间节点");
        Node fast = head;
        Node slow = head;
        if (fast.next == null){
            System.out.println("只有一个元素");
            return true;
        }
        /**
         * 快的一次走两步,慢的一次走一步那么最后快的结束了慢的走了一半
         */
        while (fast.next !=null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        Node leftLink = null;
        Node rightLink = null;
        /**
         * 获取中间结点左右两部分,反转左侧部分。
         * fast.next == null :节点数目为奇数,且slow一定为为中间节点
         * fast.next.next  == null :节点数目为偶数,slow、slow.next 均为中心结点
         */
        rightLink = slow.next;
        if (fast.next  == null){
            leftLink = inverseLinkListToEnd(slow).next;
        }else {
            leftLink = inverseLinkListToEnd(slow);
        }
        /**
         * 从此处开始同步向两边比较
         */
        return TFResult(leftLink, rightLink);
    }
    /**
     * 比较是否为回文
     * @param left
     * @param right
     * @return
     */
    public boolean TFResult(Node left, Node right){

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

        return true;
    }


    /**
     * 反转中间结点的左半部分,返回以end结点为头节点的链表。
     * @param end
     * @return
     */
    public Node inverseLinkListToEnd(Node end) {
        Node pre = null;
        Node cur = head;
        Node next = null;

        /**
         * 反转中间结点之前的结点
         */
        while (cur!=end){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        cur.next = pre;
        return cur;
    }

参与评论