精华内容
下载资源
问答
  • 比如链表要从中间节点那里开始反转 找到的中间节点是 n/2+1个节点 最终对比头尾指针时,偶数情况下只需要比较左边指针等于右边指针即可,奇数情况下相当于左边指针多走一步,需要判断右边指针不能等于空 /** * ...

    这题感觉细节比较多

    比如链表要从中间节点那里开始反转 找到的中间节点是 n/2+1个节点

    最终对比头尾指针时,偶数情况下只需要比较左边指针等于右边指针即可,奇数情况下相当于左边指针多走一步,需要判断右边指针不能等于空

    /**
     * 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;
            }
            ListNode mid=findMid(head);
            System.out.println(mid.val);
            ListNode newhead=reverse(mid);
            while(head!=newhead && newhead!=null){  
                // 这一步不可以写(head.next!=newhead)
                // 否则head为null报错
                System.out.println(head.val+" "+newhead.val);
                if(head.val!=newhead.val){
                    return false;
                }
                // if(head.next==newhead){
                //     break;
                // }
                head=head.next;
                newhead=newhead.next;
            }
            return true;
        }
        public ListNode findMid(ListNode head){
            ListNode low=head;
            ListNode fast=head;
            while(fast!=null && fast.next!=null){
                low=low.next;
                fast=fast.next.next;
            }
            return low;
        }
    
        public ListNode reverse(ListNode head){
            ListNode newhead=null;
            ListNode next=null;
            ListNode cur=head;
            while(cur!=null){
                next=cur.next;
                cur.next=newhead;
                newhead=cur;
                cur=next;
            }
            return newhead;
        }
    }

    另一种前后回文判断的方式是判断左指针不等于右指针,:

     

    展开全文
  • 判断一个链表是否回文 public class Nowcoder { public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public clas...
    判断一个链表是否回文
    public class Nowcoder {
        public class ListNode {
            int val;
            ListNode next = null;
    
            ListNode(int val) {
                this.val = val;
            }
        }
    
        public class Partition {
            public int length(ListNode pHead) {//求链表长度
                int len = 0;
                ListNode c = pHead;
                while (c != null) {
                    len++;
                    c = c.next;
                }
                return len;
            }
    
            public ListNode reverse(ListNode pHead) {//反转链表
                ListNode result = null;
                ListNode c = pHead;
                while (c != null) {
                    ListNode next = c.next;
                    c.next = result;
                    result = c;
                    c = next;
                }
                return result;
            }
    
            public boolean chkPalindrome(ListNode pHead) {
                int len = length (pHead);
                int haifLen = len / 2;
                ListNode middle = pHead;
                for (int i = 0; i < haifLen; i++) {//让middle先走一半
                    middle = middle.next;
                }
                ListNode r = reverse (middle);//再逆置后一半
                ListNode c1 = pHead;
                ListNode c2 = r;
                while (c1 != null && c2 != null) {
                    if (c1.val != c2.val) {
                        return false;
                    }
                    c1=c1.next;
                    c1=c2.next;
                }
                return true;
            }
        }
    }
    
    
    
    

     

    展开全文
  • 给定一个链表,请判断链表是否回文结构。 点此查看字符串的回文结构 以下是本篇文章正文内容,下面案例可供参考 解题思路 1. 找中间结点位置 定义两个快慢结点,快的两个两个跑,慢的一个一个跑,当快的跑完...


    题目描述

    给定一个链表,请判断该链表是否为回文结构。

    点此查看字符串的回文结构


    以下是本篇文章正文内容,下面案例可供参考

    解题思路

    1. 找中间结点位置

    定义两个快慢结点,快的两个两个跑,慢的一个一个跑,当快的跑完链表时,慢的刚好在中间结点

    2. 反转中间之后

    将中间结点赋给prev,利用之前学过的反转链表(点击蓝字查看),将中间之后的结点反转

    3. 判断是否相等

    比较前半段与后半段的结点是否相同,判断符合回文结构

    代码如下

    import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param head ListNode类 the head
         * @return bool布尔型
         */
        //1.找到中间结点
        public ListNode middle(ListNode head){
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
        public boolean isPail (ListNode head) {
            // write code here
            //2.反转中间之后
            ListNode prev = middle(head);
            ListNode cur = prev.next;
            while(cur != null){
                ListNode curNext = cur.next;
                cur.next = prev;
                prev = cur;
                cur = curNext;
            }
            //3.比较
            ListNode pa = head;
            while(pa!=prev){
                if(pa.val != prev.val){
                    return false;
                }
                pa = pa.next;
                prev = prev.next;
                if(pa.next == prev){
                    return true;
                }
            }
            return true;
        }
    }
    

    优化后:

    /**
     * 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; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null||head.next == null){
                return true;
            }
            
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
    
            ListNode prev = null;
            while(slow != null){
                ListNode curNext = slow.next;
                slow.next = prev;
                prev = slow;
                slow = curNext;
            }
            ListNode pa = head;
            while(pa!=null&&prev!=null){
                if(pa.val != prev.val){
                    return false;
                }
                pa = pa.next;
                prev = prev.next;
            }
            return true;
        }
    }
    

    总结

    如果本文对你有所帮助,要记得点赞评论哦~
    若是有描述不准确的地方,欢迎大家评论区指正,一起学习~

    展开全文
  • 判断链表回文结构1.题目2.分析3.代码示例 1.题目 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否回文...

    判断链表的回文结构

    1.题目

    对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

    给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

    测试样例:
    1->2->2->1
    返回:true

    2.分析

    对于一个回文链表可以发现,当指针节点在对其进行遍历时,走到中间位置就等同于从中间倒着往前走
    如 1->2->3->2->1,1->2->2->1
    所以可以将中间以后的部分视为前半部分的反转
    因此可以将中间以后的部分进行反转,就能得到一个和前半部分相同的链表,这也变成了判断回文结构的条件

    3.代码示例

    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            // write code here
            if(A==null||A.next==null){
                return false;
            }
            if(A.next.next==null){
                return false;
            }
           //首先定义快慢指针得到链表的中间节点
            ListNode slow = A;
            ListNode fast = A;
            while(fast!=null&&fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            //从链表的中间开始反转后续链表
            ListNode tmp = slow;
            ListNode cur = slow.next;
            ListNode curNext = cur.next;
            while(curNext!=null){
                cur.next=tmp;
                tmp=cur;
                cur=curNext;
                curNext=curNext.next;
            }
            slow.next=null;
            cur.next=tmp;
            //逐个对比前半部分链表和后半部分链表的反转
             while(cur!=null){
                 if(cur.val!=A.val){
                     return false;
                 }
                 cur=cur.next;
                 A=A.next;
             }
            return true;
        }
    }
    

    在这里插入图片描述

    展开全文
  • Java判断链表是否回文结构 回文结构序列是指顺读和反读都一样的序列 空间复杂度:O(1) 时间复杂度:O(n) /** * 判断链表是不是回文结构 * @param head 链表的头结点 * @return true 是, false 否 */ ...
  • 判断一个链表是否回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true思路:1.通过快慢指针,来遍历链表,当快指针走到末尾时,慢指针即指向链表中点2.将后半段...
  • 给定一个单链表,请判断链表是否是一个回文链表。所谓回文链表,就是链表从前往后和从后往前是一样的。 例如: 1、2、2、1 就是一个回文链表 1、2、1、1 就不是一个回文链表 常规思路: 这题的常规思路比较容易,...
  • 那么如何判断链表是否回文结构?思路是这样的: 1.先找到链表的中间结点 2.中间节点往后 对后面的结点进行逆置 3.对比前后两个链表的内容是不是完全一样 代码实现: public boolean chkPalindrome(ListNode ...
  • 度为O(1)的算法,判断是否回文结构。给定一个链表的头 指针A,请返回一个bool值,代表其是否回文结构。保证链 表长度小于等于900。 测试样例: 1->2->2->1 返回:true 问题解析 找到中间节点,然后...
  • 给定一个链表的头指针,返回一个 bool 值,true 代表其为回文结构,false 代表不是。 思路: 1.先找到中间结点,然后以中间结点为头节点,逆置链表后半部分 2.然后遍历两个链表 当两个链表对应结点的值都相等时,...
  • 1就不是回文链表,那么如何判断一个链表是否回文链表呢?如果我们知道如何判断一个字符串是否是回文,那么借助辅助空间使用同样的思想判断即可。 例如,使用一个ArrayList来存放遍历链表得到的val,然后使用左右...
  • 回文:就是正序输出和逆序输出的顺序一致。 给出了两种方式(原来有三种,第三种太复杂,被我pass了)package LinkedList;import java.util.Stack;/** * @author:MindMrWang *2017年12月4日 *:function: */ ...
  • * 判断一个链表是否回文结构【题目】 给定一个链表的头节点head,请判断链表是否回文结构。 * 例如: 1-&gt;2-&gt;1,返回true。 1-&gt;2-&gt;2-&gt;1,返回true。15-&gt;6-&...
  • public class LinkedList { //请判断一个链表是否回文链表 class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public boolean isPalindr...
  • 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断是否回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否回文结构。保证链表长度小于等于900。 测试样例: 1->2...
  • 给定一个链表,请判断链表是否回文结构。 示例1 输入 [1,2,2,1] 返回值 true 对于一个回文链表可以发现,当指针节点在对其进行遍历时,走到中间位置就等同于从中间倒着往前走 如 1->2->3->2-&...
  • 判断一个链表是否回文链表 请判断一个链表是否回文链表。 ​ 示例 1: ​ 输入: 1->2 输出: false 示例 2: ​ 输入: 1->2->2->1 输出: true //O(n)空间和时间复杂度 class Solution { public ...
  • 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断是否回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否回文结构。保证链表长度小于等于900。 示例: 1->2->...
  • 链表——回文链表

    2020-01-13 23:43:43
    判断一个链表是否回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? C语言实现 初步思路 按照描述,...
  • 给定一个链表的头节点head,请判断链表是否回文结构。 例如: 1-&gt;2-&gt;1,返回true。 1-&gt;2-&gt;2-&gt;1,返回true。15-&gt;6-&gt;15,返回true。 1-&gt;2-&gt;3,...
  • 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断是否回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否回文结构。保证链表长度小于等于900。   回文结构示例:...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 198
精华内容 79
关键字:

判断链表是否回文java

java 订阅