精华内容
下载资源
问答
  • JAVA 判断 回文链表

    2018-11-14 16:49:44
    回文链表: 什么是回文链表呢: 简单来说就是类似于这样的链表: 1 --> 2 --> 2 --> 1 --> null  但是也有一些其他的类型,比如 :空链表: null;  只有一个节点的链表: 1 ...

    回文链表:

    什么是回文链表呢:

    简单来说就是类似于这样的链表:  1 --> 2 --> 2 --> 1 -->  null 

    但是也有一些其他的类型,比如     :空链表:  null;

                                                                只有一个节点的链表:  1 --> null 

                                                                节点个数为奇数的链表:  1 --> 2 --> 3 --> 2 --> 1 -->  null 

    上面这些链表也是回文链表;所以我们在进行判断时要注意这些点;

     

    回文链表的判断:

    方法1:

    新建一个数组 arr[ ] ;遍历一次链表;按顺序将链表节点中的数据存入数组;

    然后进行数据的比较;

     

    然后依次比较 arr[A] 和 arr [B]  中的数据;

    如果数据相同,则  A++   ,B--;当两个下标相遇时;则可以判断这是一个回文链表

    如果数据不同,则不是回文链表;

    要点:

    但是在新建数组的时候,我们必须要考虑到链表的可能长度;如果链表非常非常长,就需要一个非常非常大的数组;

    这可能不是我们所希望的;

    或者我们其实可以只保存链表 前一半 或者 后一半的数据;然后将数组中这一半数据域链表中另一半数据进行比较;

     

    方法2:

    遍历一遍链表;

    求出总得节点个数为:count ;

    逆置前  count / 2  个节点;这样我们就将一个链表变为两个链表;

    然后判断这两个链表是否相同;相同的话就是回文链表。不同就不是问文链表

    要点:

    当 count  为偶数时,可以将链表平等的分为两部分;

    当 count 为奇数时,是无法平等的分为两部分的;这是进行的比较也应该进行一点点的处理;

     

     

    代码实现:

    我们在调用这个判断方法时,只需将链表头结点传入即可;

    回文链表返回 :true

    否则返回:false

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    
    class Solution {
        public boolean isPalindrome(ListNode head) {
            
            if(head==null || head.next==null){
                return true;                 //空链表和一个节点的链表都是回文链表
            }
            
           int count=0;
            
           ListNode start=head;
            
            while(start!=null){              //遍历链表得到链表节点个数
                count++;            
                start=start.next;            
            }
            
             if(count==2){                     //只有两个节点的情况
                if(head.val==head.next.val){
                    return true;
                }
                return false;
            }
                 
           int ret=count/2;
            
            start=head;
            
            ListNode temp=head.next;
            
            head.next=null;       
                    
            for(int i=1;i<ret;i++){    //至少四个节点     //逆置前一半的链表
                
                head=temp;
                temp=temp.next;
                
                head.next=start;
                start=head;                   
            }
            
            if(count%2==1){
                    temp=temp.next;
                }
            
            while(temp!=null){               //节点比较
                           
                if(temp.val!=head.val){
                    return false;
                }
                temp=temp.next;
                head=head.next;
            }
            
            return true;
                 
        }
    }

     

     

     

     

     

     

     

     

     

     

    
     

     

     
     

     

     

    展开全文
  • leetcode-java-回文链表

    2021-05-08 08:50:56
    判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? //Definition for singly-linked...

    题目描述

    请判断一个链表是否为回文链表。

    示例 1:

    输入: 1->2
    输出: false
    示例 2:

    输入: 1->2->2->1
    输出: true
    进阶:
    你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

    //Definition for singly-linked list.
     public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
    

    官方解答

    一共为两个步骤:

    1.复制链表值到数组列表中。
    2.使用双指针法判断是否为回文。

    第一步,我们需要遍历链表将值复制到数组列表中。我们用 currentNode 指向当前节点。每次迭代向数组添加 currentNode.val,并更新 currentNode = currentNode.next,当 currentNode = null 时停止循环。

    执行第二步的最佳方法取决于你使用的语言。在 Python 中,很容易构造一个列表的反向副本,也很容易比较两个列表。而在其他语言中,就没有那么简单。因此最好使用双指针法来检查是否为回文。我们在起点放置一个指针,在结尾放置一个指针,每一次迭代判断两个指针指向的元素是否相同,若不同,返回 false;相同则将两个指针向内移动,并继续判断,直到两个指针相遇。

    在编码的过程中,注意我们比较的是节点值的大小,而不是节点本身。正确的比较方式是:node_1.val == node_2.val,而 node_1 == node_2 是错误的。

    class Solution {
        public boolean isPalindrome(ListNode head) {
            List<Integer> vals = new ArrayList<Integer>();
    
            ListNode currentNode = head;
            while(currentNode != null){
                vals.add(currentNode.val);
                currentNode = currentNode.next;
            }
    
            int front = 0;
            int back = vals.size()-1;
            while(front<back){
                if(!vals.get(front).equals(vals.get(back))){
                    return false;
                }
                front++;
                back--;
            }
            return true;
        }
    }
    

    在这里插入图片描述

    民间高手解答

    fast走到末尾,slow刚好到中间。其中pre跟随slow,帮助prepre实现前半部分反转。
    但是破坏了链表

    public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) {
                return true;
            }
            ListNode slow = head, fast = head;
            ListNode pre = head, prepre = null;
            while(fast != null && fast.next != null) {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
                pre.next = prepre;
                prepre = pre;
            }
            if(fast != null) {
                slow = slow.next;
            }
            while(pre != null && slow != null) {
                if(pre.val != slow.val) {
                    return false;
                }
                pre = pre.next;
                slow = slow.next;
            }
            return true;
        }
    

    在这里插入图片描述
    不破坏链表

    public boolean isPalindrome(ListNode head) {
            //快慢指针找链表的中间节点
            ListNode fastNode = head;
            ListNode slowNode = head;
            while (fastNode != null && fastNode.next != null) {
                fastNode = fastNode.next.next;
                slowNode = slowNode.next;
            }
            //从中间节点开始反转链表
            ListNode pre = null;//pre节点为反转链表的头节点
            ListNode next;
            while (slowNode != null) {
                next = slowNode.next;
                slowNode.next = pre;
                pre = slowNode;
                slowNode = next;
            }
            ListNode right = pre;
            ListNode left = head;
            //两个节点同时开始遍历
            boolean res = true;
            while (right != null) {
                if (left.val != right.val) {
                    res = false;
                    break;
                }
                left = left.next;
                right = right.next;
            }
            //还原链表,把之前反转的链表再反转回来(为了不改变原链表的结构,所以要把破坏的原链表再还原回来)
            ListNode pre2 = null;
            ListNode next2;
            while (pre != null) {
                next2 = pre.next;
                pre.next = pre2;
                pre2 = pre;
                pre = next2;
            }
            return res;
        }
    
    

    在这里插入图片描述

    用栈

    class Solution {
        public boolean isPalindrome(ListNode head) {
            LinkedList<Integer> stack = new LinkedList<Integer>();
            ListNode tmp = head;
            while(tmp != null){
                stack.push(tmp.val);
                tmp = tmp.next;
            }  //先顺序压栈
            ListNode tmp2 = head;
            while(tmp2 != null){
                if(tmp2.val != stack.pop()){//逆序出栈比较
                    return false;
                }
                tmp2 = tmp2.next;
            }
            return true;
        }
    }
    

    在这里插入图片描述
    转换为字符串,效率低下

    class Solution {
        public boolean isPalindrome(ListNode head) {
            StringBuffer buffer = new StringBuffer();
            while (head != null) {
                buffer.append(head.val);
                head = head.next;
            }
            return strIsPalindrome(buffer.toString());
        }
    
        public boolean strIsPalindrome(String s) {
            int left = 0, right = s.length() - 1;
            while (left < right) {
                if (s.charAt(left) != s.charAt(right)) return false;
                left++;
                right--;
            }
            return true;
        }
    }
    

    剖析

    本质上就是单链表反转:

    方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。//浪费空间,如官方解法。

    方法2:使用3个指针遍历单链表,逐个链接点进行反转。//(改变了链表),如民间解法一。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    依次将旧链表上每一项添加在新链表的后面,然后新链表的头指针NewH移向新的链表头,如下图所示。此处需要注意,不可以上来立即将上图中P.next直接指向NewH,这样存放2的地址就会被丢弃,后续链表保存的数据也随之无法访问。而是应该设置一个临时指针tmp,先暂时指向P.next指向的地址空间,保存原链表后续数据。然后再让P.next指向NewH,最后P=tmp就可以取回原链表的数据了,所有循环访问也可以继续展开下去。

    while (p != NULL)                 //一直迭代到链尾
        {
            Node tmp = p.next;          //暂存p下一个地址,防止变化指针指向后找不到后续的数
            p.next = newH;               //p.next指向前一个空间
            newH = p;                     //新链表的头移动到p,扩长一步链表
            p = tmp;                   //p指向原始链表p指向的下一个空间
        }
    

    方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾。//(没有新建链表,省内存)

    就地反转即:不增加新的链表在该链表上进行反转
    原链表:dummy->1->2->3->4->5
    循环一次:dummy->2->1->3->4->5
    循环二次:dummy->3->2->1->4->5
    循环三次:dummy->4->3->2->1->5
    循环四次:dummy->5->4->3->2->1
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    public ListNode reverseList1(ListNode head) {
            if (head == null)
                return head;
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode p = dummy.next;
            ListNode q = p.next;
            while (q != null) {
                p.next = q.next;  //p指向q的下一个
               q.next = dummy.next;//q指向原来的第一个
                dummy.next = q;//dummy指向q
                q = p.next;//新的q
            }
            return dummy.next;
        }
    

    方法4:
    递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑用递归来解决。但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归来解决。或者说,因为单链表本身的结构也有自相似的特点,所以可以考虑用递归来解决)

    现在需要把A->B->C->D进行反转,
    可以先假设B->C->D已经反转好,已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体,让这个整体的next指向A,所以问题转化了反转B->C->D。那么,
    可以先假设C->D已经反转好,已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体,让这个整体的next指向B,所以问题转化了反转C->D。那么,
    可以先假设D(其实是D->NULL)已经反转好,已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体,让这个整体的next指向C,所以问题转化了反转D。
    上面这个过程就是递归的过程,这其中最麻烦的问题是,如果保留新链表的head指针呢?

    • 非递归方式是从前面数1开始往后依次处理,而递归方式则恰恰相反,它先循环找到最后面指向的数5,然后从5开始处理依次翻转整个链表。
    • 首先指针H迭代到底如下图所示,并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数,所以整个过程NewH指针一直指向存放5的地址空间。
      在这里插入图片描述
    • 然后H指针逐层返回的时候依次做下图的处理,将H指向的地址赋值给H.next.next指针,并且一定要记得让H.next =NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层H.next.next赋值的时候会覆盖后续的值。
      在这里插入图片描述
      在这里插入图片描述
    Node In_reverseList(Node H)
    {
        if (H == NULL || H.next == NULL)       //链表为空直接返回,而H.next为空是递归基
            return H;
        Node newHead = In_reverseList(H.next); //一直循环到链尾 
        H.next.next = H;                       //翻转链表的指向
        H.next = NULL;                          //记得赋值NULL,防止链表错乱
        return newHead;                          //新链表头永远指向的是原链表的链尾
    }
    
    展开全文
  • 判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 可以考虑分为两步考虑: (1)复制链表到数组列表中 (2)使用双指针判断是否是回文 二、...

    一、题解

    请判断一个链表是否为回文链表。

    示例 1:

    输入: 1->2
    输出: false

    示例 2:

    输入: 1->2->2->1
    输出: true

    可以考虑分为两步考虑

    (1)复制链表到数组列表中
    (2)使用双指针判断是否是回文

    二、代码

    class Solution {
        public boolean isPalindrome(ListNode head) {
            List<Integer> list= new ArrayList<Integer>();
    
            // 将链表的值复制到数组中
            ListNode root= head;
            while (root!= null) {
                list.add(root.val);
                root= root.next;
            }
    
            // 使用双指针判断是否回文
            int first= 0;
            int last= list.size() - 1;
            while (first< last) {
                if (!list.get(first).equals(list.get(last))) {
                    return false;
                }
                first++;
                last--;
            }
            return true;
        }
    }
    

    三、总结

    1. Interger 包装类,不能直接使用 == 比较,需要使用 equals

    在这里插入图片描述

    public class Test {
        public static void main(String[] args) {
            Integer a = 1;
            Integer b = 1;
            System.out.println(a.equals(b));
        }
    }
    

    (2)List 接口的常用操作:
    在这里插入图片描述

    List 接口继承 Collection 接口,所以 其中的 size() 方法也常用。

    展开全文
  • 判断回文链表

    2018-09-16 11:11:00
    题目描述:判断一个普通的链表是否是回文链表,要求时间复杂度O(n),空间复杂度O(1) 解决思路: 最简单的方法是利用栈把链表的前半段压栈,然后出栈与链表的后半段逐个比对。找中间位置的方法是快慢指针。 还有一...

    题目描述:判断一个普通的链表是否是回文链表,要求时间复杂度O(n),空间复杂度O(1)


    解决思路:

    • 最简单的方法是利用栈把链表的前半段压栈,然后出栈与链表的后半段逐个比对。找中间位置的方法是快慢指针。
    • 还有一种方法是利用快慢指针找到中间,然后将链表的后半部分反转,再依次进行比较,利用的是链表反转的知识。
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    import java.util.Stack;
    
    
    public class Main_ {
    
        class ListNode{
            public int val;
            ListNode next = null;
    
            public ListNode(int val){
                this.val = val;
            }
        }
    
        //利用栈的思想
        public boolean checkPalindrom(ListNode node){
            if(node == null)
                return false;
            Stack<ListNode> stack = new Stack<>();
            ListNode fast = node;
            ListNode slow = node;
            while (fast != null && fast.next != null){
                stack.push(slow);
                slow = slow.next;
                fast = fast.next.next;
            }
            //如果为奇数个
            if(fast != null)
                slow = slow.next;
            while (!stack.isEmpty()){
                if(stack.pop().val != slow.val)
                    return false;
                slow = slow.next;
            }
    
            return true;
        }
    
        //利用链表反转的思想
        public boolean checkPalindrom_(ListNode node){
            if(node == null)
                return false;
            ListNode fast = node;
            ListNode slow = node;
            while (fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
    
            while (fast != null)
                slow = slow.next;
            ListNode p = slow.next;
            ListNode q = slow.next.next;
            slow.next = null;
            while(p != null){
                p.next = slow;
                slow = p;
                p = q;
                if(q.next != null)
                    q = q.next;
            }
            while (slow != null){
                if(slow.val != node.val)
                    return false;
                slow = slow.next;
                node = node.next;
            }
    
            return true;
        }
    
        public static void main(String[] args) {
            ListNode node1 = new Main_().new ListNode(1);
            ListNode node2 = new Main_().new ListNode(2);
            ListNode node3 = new Main_().new ListNode(3);
            ListNode node4 = new Main_().new ListNode(3);
            ListNode node5 = new Main_().new ListNode(1);
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;
            node5.next = null;
            System.out.println(new Main_().checkPalindrom(node1));
            System.out.println(new Main_().checkPalindrom(node1));
        }
    }
    
    展开全文
  • Java回文链表

    2019-10-14 12:35:20
    题目:请判断一个链表是否为回文链表。 示例 1: 输入: [1,2] 输出: false 示例 2: 输入: [1,2,2,1] 输出: true 示例3: 输入[1,2,2,3] 输出:false 使用方法:将链表保存到数组中,按照数组回文判断方式进行判断 ...
  • leetcode-java 回文链表

    2019-11-28 19:34:41
    判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? 问题分析: 回文的思想就是...
  • 判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true思路:1.通过快慢指针,来遍历链表,当快指针走到末尾时,慢指针即指向链表中点2.将后半段...
  • if (fast != null) slow = slow.next;
  • public static boolean isPalindrome(String str){ if(str.length()==0||str.length()==1){ return true; } int leftIndex = 0; int rightIndex = str.length()-1; ... while (leftIndex<...
  • 给定一个单链表,请判断该链表是否是一个回文链表。所谓回文链表,就是链表从前往后和从后往前是一样的。 例如: 1、2、2、1 就是一个回文链表 1、2、1、1 就不是一个回文链表 常规思路: 这题的常规思路比较容易,...
  • // 翻转链表 public ListNode reverseList(ListNode head) { if (head == null) return null; ListNode cur = head, pre = null, curNext = head.next; while (cur != null) { curNext = cur.next; cur.next = ...
  • 这段时间完成了职业生涯第一次跳槽,对算法题目有了一个更深的认识和理解,这里将...判断回文链表 在前面几个小节的介绍中,我们主要介绍了基础的链表题目,主要是利用了双指针的思想。本篇博文,我们来看三道经典...
  • 判断一个链表是否为回文链表判断一个链表是否为回文链表。 ​ 示例 1: ​ 输入: 1->2 输出: false 示例 2: ​ 输入: 1->2->2->1 输出: true //O(n)空间和时间复杂度 class Solution { public ...
  • 题目:请判断一个链表是否为回文链表。 思考:能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题? 分析:题目默认链表为单链表,因为链表与数组不同,数组支持随机访问,根据下标随机访问的时间复杂度为O(1),...
  • Java实现 LeetCode 234 回文链表

    万次阅读 多人点赞 2020-03-02 21:03:04
    判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? /** * Definition for singly-...
  • 回文链表 java

    2020-10-09 17:42:42
    判断一个链表是否为回文链表。 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 解题思路(参考题解) 空链表和单结点链表都属于回文链表 数组 使用数组存放链表元素,从数组开始和...

空空如也

空空如也

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

java判断回文链表

java 订阅