精华内容
下载资源
问答
  • 【题目描述】:给定一个单链表,例如 1->2->3->2->1,即为回文链表,如果为 1->...首先声明一个单链表(此声明可以是Java内部类,也可以是外部类,进行import): class Node{ ...

    【题目描述】:给定一个单链表,例如 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),但是比上面那个方法要稍微好点。具体代码如下:
    
    算法图解:
    

    算法图解

     //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)。具体代码如下:
    算法图解:
    

    在这里插入图片描述

    //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++;
        }
    

    以上代码如有问题,还请指正!

    展开全文
  • 回文单链表java

    2020-10-15 13:07:18
    如何判断一个单链表回文单链表? LeetCode题目链接 下面是LeetCode的题目截图: 思路分析 回文单链表:链表反转后和原链表一样 思路一:根据回文单链表的特点很容易分析出 ① 反转单链表 ② 遍历比较原链表和...

    如何判断一个单链表是回文单链表?

    思路分析

    回文单链表:链表反转后和原链表一样

    1. 思路一:根据回文单链表的特点很容易分析出
      ① 反转单链表
      ② 遍历比较原链表和反转后的链表,如果有不一样的结点,说明不是回文的,如果两链表完全一样,说明是回文的
    2. 思路二
      ① 使用快慢指针找出链表的中间结点,其中快指针步长为2,慢指针步长为1
      根据中间结点反转后半部分链表
      ③ 遍历比较前后两部分链表的结点是否一致

    反转实现

    由于两个思路都需要反转,这里先实现一下单链表反转

    • 图示
      在这里插入图片描述
    • 代码实现
    public static ListNode reverseLinked(ListNode head) {
            // 当前结点
            ListNode cur = head;
            // 反转后的链表
            ListNode listNode = null;
            // 遍历原链表,构造反转链表
            while (cur != null) {
                // 临时保存当前结点的下个结点
                ListNode nextTemp = cur.next;
                // 下面两行代码表示,每次遍历都让当前结点作为临时链表的开始结点
                cur.next = listNode;
                listNode = cur;
                // 结点后移,继续遍历
                cur = nextTemp;
            }
            return listNode;
        }
    

    思路一实现

    public boolean isPalindrome(ListNode head) {
            // 反转链表
            ListNode reservedListNode = reverseLinked(head);
            // 遍历比较原链表和反转后链表的结点
            ListNode cur = head;
            ListNode cur1 = reservedListNode;
            while (cur != null && cur1 != null) {
                if (cur.val != cur1.val) {
                    return false;
                }
                // 后移,继续遍历比较
                cur = cur.next;
                cur1 = cur1.next;
            }
            return true;
        }
    

    思路二实现

    • 图示
      在这里插入图片描述
      在这里插入图片描述
      结点个数为奇数:当满足fast.next = null时,slow指向中间结点
      结点个数为偶数:当满足fast.next.next = null时,slow指向中间结点

    • 代码实现

    public boolean isPalindrome2(ListNode head) {
            // 使用快慢指针找出中间结点
            ListNode middle = getMiddle(head);
            // 反转后半部分链表
            ListNode reverseLinked = reverseLinked(middle);
            // 比较前后两部分链表
            ListNode cur = head;
            ListNode cur1 = reverseLinked;
            while (cur != null && cur1 != null) {
                if (cur.val != cur1.val) {
                    return false;
                }
                // 后移
                cur = cur.next;
                cur1 = cur1.next;
            }
            return true;
        }
    
        private static ListNode getMiddle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            // 不管链表结点个数是奇数还是偶数,循环退出,slow就是中间结点
            return slow;
        }
    
    展开全文
  • 单链表回文序列

    2019-01-21 21:38:48
    回文序列 借助数组 public boolean isPalindrome(LinkList&lt;T&gt; L) // 回文链表数组法 { Node&lt;T&gt; p =L.head.next; int i=0; int temp=0; while(p!=null) { i++; ...

    回文序列

    • 借助数组

    public boolean isPalindrome(LinkList<T> L)    // 回文链表数组法
    	{
    		Node<T> p =L.head.next;
    		int i=0;
    		int temp=0;
    		while(p!=null)
    		{
    			i++;
    			p = p.next;
    		}
    		p = L.head.next;
    		int[] Array = new int[i];
    		for(int a=0;a<i;a++)
            {
                Array[a] = (Integer) p.data;
                p = p.next;
            }
            for(int b=0,c=Array.length-1;b<c;b++,c--)
            {
                if(Array[b]!=Array[c])
                {
                    temp = 1;
                    break;
                }
            }
            if(temp==1)
                return false;
            else
                return true;
    	}

     借助数组的回文序列较为简单在此我不做过多的讲解

     

    展开全文
  •   回文结构:如1-2-2-1;1-2-3-2-1;类似于这样的就是回文结构,可以发现链表正向和反向的内容顺序是一样的。     算法思路:   ①可以先找到链表的中间节点,将后半部分进行反转   ②对反转后的链表进行...

      回文结构:如1-2-2-1;1-2-3-2-1;类似于这样的就是回文结构,可以发现链表正向和反向的内容顺序是一样的。


      算法思路
      ①可以先找到链表的中间节点,将后半部分进行反转
      ②对反转后的链表进行前后部分数据域的比较,如果数据域相同,head=head.next;slow=slow.next,如果比较完之后两个指针相遇,则代表链表是回文结构(在这里要注意链表节点数是偶数个的情况要单独判断一下)

    在这里插入图片描述

    参考代码

    class ListNode{
        public int data;
        public ListNode next;
    
        public ListNode(int data){
            this.data=data;
            this.next=null;
        }
    }
    
    class MyList{
        public ListNode head;
    
        public MyList(){
            this.head=null;
        }
    
        //尾插法建立单链表
        public void addLast(int data){
            ListNode node=new ListNode(data);
            if(this.head==null){
                this.head=node;
            }else {
                ListNode cur = this.head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next=node;
            }
    
        }
    
    
        //链表的回文结构判断
        public boolean isPalindrome() {
            if(this.head==null){
                return true;
            }
    
            ListNode fast=this.head;
            ListNode slow=this.head;
           //找链表的中间节点
            while(fast!=null && fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
           //将后半部分进行反转
            ListNode p=slow.next;
            while(p!=null){
                ListNode pnext=p.next;
                //反转
                p.next=slow;
                slow=p;
                p=pnext;
            }
            
          //slow往前  head往后    data域不一样返回false   直到相遇
            while(this.head!=slow){
                if(this.head.data!=slow.data){
                    return false;
                }
                //偶数情况判断
                if(this.head.next==slow){
                    return true;
                }
                head=head.next;
                slow=slow.next;
            }
            return true;
        }
        
         //打印单链表
        public void display(){
            ListNode cur=head;
            while(cur!=null){
                System.out.print(cur.data+" ");
                cur=cur.next;
            }
            System.out.println();
        }
    }
    
    
    
    public class Test {
        public static void main(String[] args) {
            MyList my = new MyList();
            my.addLast(1);
            my.addLast(2);
            my.addLast(0);
            my.addLast(2);
            my.addLast(1);
            my.display();
            boolean a=my.isPalindrome();
            if(a==true){
                System.out.println("是回文结构");
            }else{
                System.out.println("不是回文结构");
            }
        }
    }
    
    
    //打印结果
    
    1 2 0 2 1 
    是回文结构
    
    

      上述方法是将单链表的结构进行了改变之后进行判断

    展开全文
  • 链表的回文结构,即 1 --> 2 --> 3 --> 2 --> 1 这样的形式,链表正着和反过来是一样的。 1 时间复杂度 O(N) 思路: 1、将原链表进行拷贝; 2、对拷贝的链表进行逆置; 3、然后比较逆置之后的链表和原链表是否相同...
  • java回文单链表

    2019-09-28 21:06:27
    wrong了好多次就是过不了 过不了 画图板搞起! 成功AC 附代码 /** * Definition for singly-linked list. * public class ListNode { * int val;... * ListNode next;... * ListNode(int x) { val = x;...
  • 单链表——Java

    2019-11-12 17:06:07
    单链表的定义: class ListNode{ public int data; public listNode next; public ListNode(int data){ this.data=data; this.next=null; } } class MysingalList{ public ListNode head; public ...
  • 题目 判断一个单链表是否是回文链表。 如:[1, 2, 3, 2, 1] 就是一个回文链表,正着依次看链表中元素和反着依次看链表中元素都是一样的。 要求: 时间复杂度 O(n) 空间复杂度 O(1) ...
  • 判断一串数字或者一个字符串是否回文,是一个编程的基本问题。这里我根据自己最近回顾数据结构相关知识,java语言实现两个经典案例。 1.利用String存储字符串,判断是否为回文字符串。 这个解决比较简单,i和j分别...
  • 回文的意思是翻转后和原来的内容相同,例如1-0-2-0-1就是回文。因此判断一个链表是否为回文,就可以将链表反转,比较两者是否相同即可。 但是考虑到反转后,我们只需要比较一般的内容是否相等就可以判断这个链表...
  • /** * 后半部分压栈,然后依次弹出对比 * @param head * @return */ public static boolean isPalindrome2(Node head){ //首先利用快慢指针找链表中点 Node slow = head; Node fast = head;...
  • 思路 使用快慢两个指针找到链表中点,慢指针每次前进一步,快指针每次前进两步 在慢指针前进的过程中,同时修改其 next 指针,使得链表前半部分反序。 最后比较中点两侧的链表是否相等...java版本 https://github.c...
  • 给定一个单链表,请判断该链表是否是一个回文链表。所谓回文链表,就是链表从前往后和从后往前是一样的。 例如: 1、2、2、1 就是一个回文链表 1、2、1、1 就不是一个回文链表 常规思路: 这题的常规思路比较容易,...
  • 判断一个链表是否是回文
  • Java单链表

    2019-11-18 19:46:06
    Java单链表代码 class ListNode { public int data; public ListNode next; public ListNode(int data) { this.data = data; this.next = null; } } class MySingleList { public L...
  • public boolean huiwen_double_zhen(Node head){ Node left=head; Node right; right = reverse(double_zhen(head)); while (right!=null){ if(right.data!=left.data){ return false; ... }

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,626
精华内容 650
关键字:

单链表回文java

java 订阅