【算法学习系列】Java语言判断单链表回文

缺乏、安全感 2023-06-16 07:47 67阅读 0赞

### 【题目描述】：给定一个单链表，例如 1->2->3->2->1，即为回文链表，如果为 1->2->3->3->1 即不是回文链表。给出算法，实现时间复杂度O(N),空间复杂度O(1)。 ###

### 难点：如何实现空间复杂度为O(1)的操作。 ###

##### 首先声明一个单链表（此声明可以是Java内部类，也可以是外部类，进行import）： #####

class Node{ 
            private Node next;
            private Object data;
            public Node(Object data){ 
                this.data=data;
            }
       }

##### 这里使用三种方法进行探索。 #####

#### Method1： ####

算法思想：借助栈进行实现，即将链表的元素依次进栈。全部进栈之后，由于栈先进后出的性质，栈顶的元素即为原链表中的最后一个值，然后和链表指针的移动同步依次出栈，比较每个元素，如果都相同，则肯定是回文的。这样做明显时间和空间复杂度:O(N)。具体代码如下：

//method1 ：时间和空间复杂度均为O（N）
        public boolean method1(Node head){ 
            if(head==null){ 
                return false;
            }
            Node cur=head;
            Stack<Node> stack=new Stack<Node>();
            while(cur!=null){ 
                stack.push(cur);
                //System.out.println(cur.data);
                cur=cur.next;
            }
            while(head!=null){ 
                if(!(stack.pop().data.equals(head.data))){ 
                    return false;
                }else{ 
                    head=head.next;
                }
            }
            return true;
        }

#### Method 2 : ####

算法思想：仍然借助栈进行实现，但是此时可以设置从表头开始的快慢两指针，快指针一次走两个元素，慢指针一次走一个元素，由此，当快指针到达最后一个元素时，慢指针是在中间元素的位置。然后将慢指针以及慢指针以后的元素(N/2个)依次进栈，全部进栈之后，由于栈先进后出的性质，栈顶的元素即为原链表中的最后一个值，然后和链表指针的移动同步依次出栈，直到栈或者链表指针移到慢指针所指位置为止。
    【注：这里不用考虑链表元素个数是奇数个还是偶数个，因为即使是偶数个，当慢指针在中间时，意味着用这个方法栈里面的元素比从链头到慢指针多了一个慢指针元素，在最后进行出栈比对时，进行条件判断，双方谁满足条件直接就停止了，不影响结果，具体可以自己画个图。】
    这样做明显时间复杂度:O(N)和空间复杂度:O(N/2)，当然也是O(N)，但是比上面那个方法要稍微好点。具体代码如下：
    
    算法图解：

![算法图解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70]

//method2 空间O(N/2) 时间O(N)
        public boolean method2(Node head){ 
            if(head==null){ 
                return false;
            }
            Node slow=head;
            Node quick=head;
            while(quick.next!=null && quick.next.next!=null){ 
                slow=slow.next;
                quick=quick.next.next;
               
            }
            Stack<Node> stack=new Stack<Node>();
            Node mid=slow;
            while (slow != null) { 
                stack.push(slow);
                slow = slow.next;
            }
            while(head!=mid.next && stack.size()!=0){ 
                if(!(stack.pop().data.equals(head.data))){ 
                    return false;
                }else{ 
                    head=head.next;
                }
            }
            return true;
        }

#### method 3: ####

算法思想：设置从表头开始的快慢两指针，快指针一次走两个元素，慢指针一次走一个元素，由此，当快指针到达最后一个元素时，慢指针是在中间元素的位置。然后将慢指针以及慢指针以后的元素借助几个指针逆序，然后将尾指针作为后边那部分的头指针，与原链表的头指针一起移动，依次比较元素。
    这样做明显时间复杂度:O(N)和空间复杂度:O(1)。具体代码如下：
    算法图解：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 1]

//method3 时复O(N) 空复O(1)
       public boolean method3(Node head){ 
            if(head==null){ 
                return false;
            }
            Node slow=head;
            Node quick=head;
            boolean flag=true;
            while(quick.next!=null && quick.next.next!=null){ 
                slow=slow.next;
                quick=quick.next.next;
            }
            if(quick.next!=null){ 
                quick=quick.next;
            }
            //进行逆序后半部分链表 注意不能断链
            quick=slow.next;
            slow.next=null;
            Node helpNode=null;
            //这里牵扯到逆序 那么后来要保证原Link的顺序不变
            // *** 还要记得再加个将顺序倒过来的过程
            while(quick!=null){ 
                helpNode=quick.next;
                quick.next=slow;
                slow=quick;
                quick=helpNode;
            }
            quick=head;//当作头指针
            helpNode=slow;//保证quick不为空指针 而是最后一个位置的指针
            while(quick!=null && helpNode!=null){ 
                //System.out.println("====== ");
                if(!(quick.data.equals(helpNode.data))){ 
                    flag=false;
                    break;
                }else{ 
                    quick=quick.next;
                    helpNode=helpNode.next;
                }
            }
            //after judge begin reverse the last half
            // Now slow represent the last node
            helpNode=slow.next;//倒数第二个节点
            slow.next=null;//最后一个节点指针指向NULL
            while(helpNode!=null){ 
                quick=helpNode.next;//指代helpNode的下一个节点
                helpNode.next=slow;
                slow=helpNode;
                helpNode=quick;
            }
            //测试是否已经保持原链表的格式
            helpNode=head;
            while(helpNode!=null){ 
                System.out.print(helpNode.data+" ");
                helpNode=helpNode.next;
            }
    
            return flag;
        }

##### 关于以上提到的addLink方法： #####

//前面需要有个 head 和 size 的初始化方法，一般为所在类的构造方法
     public void addLink(Object data){ 
            Node newNode=new Node(data);
            if(size==0){ 
                head=newNode;
            }else{ 
                newNode.next=head;
                head=newNode;
            }
            size++;
        }

以上代码如有问题，还请指正！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191125081417498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191125082336747.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70