精华内容
下载资源
问答
  • 2020-08-09 12:38:07

    Java判断链表是否为回文结构

    • 回文结构序列是指顺读和反读都一样的序列

    空间复杂度:O(1)
    时间复杂度:O(n)

        /**
         * 判断链表是不是回文结构
         * @param head 链表的头结点
         * @return true 是, false 否
         */
        public static boolean isHuiWen(Node head){
            if (head == null || head.next == null){
                return true;
            }
            //定义一个快节点和慢节点
            Node slow = head;
            Node fast = head;
            //最终slow会停在链表中间,指向中间节点
            while (fast.next != null && fast.next.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            //反转链表后半部分的节点
            Node revNode = reverse(slow);
            //链表头和链表尾进行比较,同时向中间前进
            while (revNode != null){
    //            System.out.println(revNode.Data);
                if (revNode.Data != head.Data){
                    return false;
                }
                revNode = revNode.next;
                head = head.next;
            }
    
            return true;
        }
    
        /**
         * 反转链表
         * @param head 链表的头结点
         * @return  返回反转后链表的头结点
         */
        public static Node reverse(Node head){
            if (head == null || head.next == null){
                return head;
            }
            Node newNode = reverse(head.next);
            head.next.next = head;
            head.next = null;
            return newNode;
        }
    
    更多相关内容
  • 比如链表要从中间节点那里开始反转 找到的中间节点是 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;
        }
    }

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

     

    展开全文
  • Java实现回文链表判断

    判断是否为回文链表

    之前做过判断是否为回文字符串的题目,用到的方法有,双指针,即一个从开始走,一个从末尾走,判断两者是否相等即可,当然其中需要注意的一个问题便是,要将大写字母都转化为小写字母

    而单向链表不同于数组结构,无法直接从后向前,于是本人进行了如下尝试:

    1、将链表中的val值全部存入LinkList中,再通过判断回文字符串的类似方法判断,LinkList是否为回文,代码如下:

    public static boolean solution01(ListNode head){
    
            LinkedList<Integer> list = new LinkedList<>();
            while (head != null){
                list.add(head.val);
                head = head.next;
            }
    
            for (int i = 0; i < list.size()/2; i++) {
                if (list.get(i) != list.get(list.size() - i - 1))
                    return false;
            }
            return true;
        }
    

    通过运行发现,正常的链表都可以判断,但是在提交的时候发现,有一个链表运行超时,点击查看,是由于leetcode提供了一个几百个结点的链表,what the fuck!这条路堵死了。

    2.直接将链表全部翻转,然后判断对应的val值是否相等

    理论上这种方式是可行的,但是,我在编写的过程中发现一个问题,在将原链表翻转后,链表自己就只剩头节点了,或者为null。因为之前实现的翻转都是返回的一个新的链表,这导致无法进行翻转后的链表与原链表进行比较了。(寄!)

    3.翻转后一半链表,与前一半链表进行比较

    由于上述方法的失败,不得不考虑新的方法,其实我们不需要翻转整个链表,我们只需要翻转后一半链表,然后与前半部分链表进行比较即可。
    问题转化如下:

    1. 获得后半部分链表
      可以使用快慢指针,快指针走两格,慢指针走一格,那么当快指针为空,或者快指针下一个为空时,慢指针就走到一半了,当然还涉及一个奇数偶数个结点的问题,如果是奇数个结点,那么慢指针应该继续向后走一格。代码如下:
    		ListNode slow = head;
            ListNode fast = head;
    
            //快指针走到头,则慢指针走到一半,获得后半部分的链表
            if (fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            
            //如果fast不为空,说明链表的长度是奇数个,则慢指针继续往后走一个
            if (fast != null){
                slow = slow.next;
            }
    

    这样就获得了后半部分的链表——slow。
    2. 翻转后半部分链表
    在或者后半部分链表后,对其进行翻转,即使其原链表发生改变也没什么影响

    slow = reverse(slow);
    
    //翻转函数如下
       public static ListNode reverse(ListNode head){
           ListNode prev = null;
           while (head != null){
               ListNode next = head.next;
               head.next = prev;
               prev = head;
               head = next;
           }
           return prev;
       }
    

    3.判断是否相等
    这段代码较为简单,以慢指针为目标进行迭代就行,如下:

    fast = head;
    while (slow != null){
        if (fast.val != slow.val)
            return false;
        fast = fast.next;
        slow = slow.next;
    }
    return true;
    

    4.总结

    针对链表的回文判断,我觉很需要掌握快慢指针的运用,同时如何获得后一半的链表的思想,也是我们应该掌握的,此类方法在后续的学习中应当常用。全文手码,如有写的不好的,不对的地方希望大家批评指正,共同进步。

    展开全文
  • 链表节点依次入栈,因为栈先进后出的特性,当链表节点全部入栈后,栈中就保存了原链表节点的逆序排列,然后将栈顶节点依次出栈并顺序与链表节点进行比较,如果在比较过程中发现节点的值不同,说明不是回文链表 ...

    方法一:
    最简单也最容易想到的方法,采用栈的数据结构,将链表节点依次入栈,因为栈先进后出的特性,当链表节点全部入栈后,栈中就保存了原链表节点的逆序排列,然后将栈顶节点依次出栈并顺序与链表节点进行比较,如果在比较过程中发现节点的值不同,说明不是回文链表

    【代码实现】

    //首先给出节点类的定义
    public class Node {
        public int val;
        public Node next;
    
        public Node(int data) {
            this.val = data;
            this.next = null;
        }
        public Node() {
        }
    }
    

    以下所有方法均假设链表没有头结点!

        public static boolean isHuiwen1(Node list) {
            Node p = list;
            Stack<Node> st = new Stack<Node>();
            while (p != null) {
                st.push(p);
                p = p.next;
            }
            p = list;
            while (!st.isEmpty()) {
                if (p.val != st.pop().val)
                    return false;
                p = p.next;
            }
            return true;
        }
    

    方法二:
    方法一是将链表节点全部入栈,但判断一个链表是不是回文链表,我们只需要顺序比较表头跟表尾节点值即可,比如说list1=1->2->3->2->1,我们只需要比较1跟1,2跟2,3跟3。所以方法二就采用了这一思想,跟方法一差不多,也用到了栈的数据结构,只不过首先要进行链表的遍历,找到链表的中间节点p,p将整个链表分成左右两部分,我们只需要将右半部分链表入栈即可

    先介绍求链表中间节点的方法
    定义两个节点p,q,分别指向头结点head和head.next,然后在p.next不为空且q.next.next不为空的条件下,循环执行——“q后移一步,p后移两步”的操作,那当p走到链表最后一个节点或者倒数第二个节点时,q刚好指向链表的中间节点,这与“求链表的倒数第K个节点的方法有异曲同工之妙”

        Node p = head, q = head.next;//q point to the middle Node
        while (p.next != null && p.next.next != null) {
            q = q.next;
            p = p.next.next;
        }
    

    此方法的代码描述

        public static boolean isHuiwen2(Node list) {
            Node head = new Node();
            head.next = list;//create a head Node
            Stack<Node> st = new Stack<Node>();
            Node p = head, q = head.next;//q finally point to the middle Node
            while (p.next != null && p.next.next != null) {
                q = q.next;
                p = p.next.next;
            }
            while (q != null) {
                st.push(q);
                q = q.next;
            }
            p = head.next;
            while (!st.isEmpty()) {
                if (p.val != st.pop().val)
                    return false;
                p = p.next;
            }
            return true;
        }
    

    方法三:

    方法三用到了链表的逆序,实际上是链表部分逆序。这一方法的思想是:首先通过链表遍历找到链表的中间节点,然后将右半部分链表进行逆序,如下图所示
    在这里插入图片描述
    然后,我们就可以通过定义两个分别指向表头跟表尾的节点,依次对链表首尾节点进行比较了呀!

        public static boolean isHuiwen3(Node list) {
            Node head1 = new Node();
            Node head2 = new Node();
            head1.next = list;
            Node p = head1, q = head1.next, r;//q point to the middle Node
    
            while (p.next != null && p.next.next != null) {
                q = q.next;
                p = p.next.next;
            }
    
            p = q.next;
            while (p != null) {
                q.next = null;
                r = p.next;
                p.next = q;
                if (r == null) {//note that p point to the last Node
                    q = p;
                    break;
                }
                q = r;
                p = q.next;
            }
    
            p = head1;
            head2.next = q;
            q = head2;
            while (p.next != null && q.next != null) {
                if (q.next.val != p.next.val) {
                    return false;
                }
                q = q.next;
                p = p.next;
            }
            return true;
        }
    

    可以看出在时间复杂度相同,都为O(N)的情况下,方法三的空间复杂度为O(1),其他两种方法都采用了栈的数据结构,时间复杂度都为O(N)

    还有要注意的一点是,不管链表是不是回文链表,方法三在结果返回前都需要将链表还原为初始结构,不能给人家把结构改了又不改回去,可以自己尝试写一下

    展开全文
  • 牛客网判断是否回文链表java)详细讲解
  • 啥是回文结构:一个链表正向看和反向看都是一样的。 例如:1 --> 2 --> 2 --> 1,1 --> 2 --> 3 --> 2 --> 1这样的链表就具有回文结构。 1、额外空间复杂度为O(1)的写法: (1)找到此链表的...
  • 判断单链表是否回文链表 (牛客网—牛客题霸算法篇—NC96) 题目描述 给定一个链表,请判断链表是否回文结构。 回文是指该字符串正序逆序完全一致。 思路 Java实现 方法一:遍历 定义三个指针,分别为left、...
  • import java.util.Stack; public class pro { public static void main(String[] args) {} public static class Node { //单链表 public int value; public Node next; public Node(int data) { this.value ...
  • 给定一个链表,请判断链表是否回文结构。 示例1 输入 [1,2,2,1] 返回值 true 对于一个回文链表可以发现,当指针节点在对其进行遍历时,走到中间位置就等同于从中间倒着往前走 如 1->2->3->2-&...
  • 方法三:利用快慢指针,找出链表中点位置,将链表后半部分翻转,依次比较两链表值,判断是否回文结构后将翻转的链表还原。 package class04P; import java.util.Stack; public class Code04P_IsPalindromeList ...
  • 思路:找到链表的中间节点,然后逆置后半段,再从两边比较对应位置是否值域相等。 代码: public boolean chkPalindrome(){ if(head==null){ return false; } if(head.next==null){ return true; } Node fast=head...
  • * 判断链表是不是回文链表 */ public class IsPalindrome { //先找到链表的中间位置分开,然后把后半部分反转,遍历作比较,遇到不等就返回false public static boolean isPalindrome(ListNode head){ if(head...
  • 如果有链表反转的基础,实现链表回文判断就简单的多,如果对反转链表不熟悉,可以参考这篇博客。思路很简单,先找到链表的中间Node,采用的快慢指针法。慢指针一次走一步,快指针一次走两步,当快指针触底的时候,慢...
  • 判断链表是否回文(空间复杂度为O(1)): 用到的有:快慢指针,链表翻转 代码: public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } Node n1 = ...
  • 给定一个链表的头结点是head,请判断链表是否回文结构 例如: 1-&gt;2-&gt;1,返回true 1-&gt;2-&gt;2-&gt;1,返回true 1-&gt;2-&gt;3,返回false 分析: 在链表问题中,...
  • 度为O(1)的算法,判断是否回文结构。给定一个链表的头 指针A,请返回一个bool值,代表其是否回文结构。保证链 表长度小于等于900。 测试样例: 1->2->2->1 返回:true 问题解析 找到中间节点,然后...
  • 作为一个java初学者,最近遇到了回文链表结构这个难题,经过一番学习总算搞清楚个大概。 先来说一下什么是回文链表,会问链表在我们生活中经常能够遇到。会问链表的结构就是 例如:1->2->3->2->1。...
  • * 判断一个链表是否回文结构 * 进阶:如果链表的长度为N,时间复杂度达到O(N),额外的空间复杂度是O(1)。 * @author lhs94 * @date 2017-10-24 */ public class JudgePalindromel { public ...
  • 判断一个链表是否回文 public class Nowcoder { public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public clas...
  • 给定一个链表,请判断链表是否回文结构。 点此查看字符串的回文结构 以下是本篇文章正文内容,下面案例可供参考 解题思路 1. 找中间结点位置 定义两个快慢结点,快的两个两个跑,慢的一个一个跑,当快的跑完...
  • //合并两个有序链表 import java.util.ArrayList; import java.util.List; public class MergeTwoLists { public static void main(String[] args) { ListNode node1 = new ListNode(1); ListNode node2 = new ...
  • 判断链表是否回文链表 leetcode JAVA-coding-interview-Balazs 帮助: 这个 repo 包含大约 300 个 Leetcode.com 和 85 个 Algoexpert.io 问题以及使用 Swift 和 Python 的解决方案 这个 repo 包含我用Java和Python...
  • 判断一个链表是否回文链表判断一个链表是否回文链表。 ​ 示例 1: ​ 输入: 1->2 输出: false 示例 2: ​ 输入: 1->2->2->1 输出: true //O(n)空间和时间复杂度 class Solution { public ...
  • 分享一个大牛的人工智能教程。零基础!通俗易懂!... * 判断一个链表是否回文结构。 * * 思路: * 不用栈和其他数据结构,只用有限几个变量。 * * @author Created by LiveEveryDay */ publi
  • 链表回文结构的判断
  • 给定一个链表的头指针,返回一个 bool 值,true 代表其为回文结构,false 代表不是。 思路: 1.先找到中间结点,然后以中间结点为头节点,逆置链表后半部分 2.然后遍历两个链表 当两个链表对应结点的值都相等时,...
  • 简单算法 判断一个链表是否回文结构(java) 描述 给定一个链表,请判断链表是否回文结构。 示例 输入: [1,2,2,1] 返回值: true 说明: 1->2->2->1 想法:先使用快慢结点找到中间结点,然后通过...
  • 链表回文判断,里面涉及到到一个反转链表的方法

空空如也

空空如也

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

判断链表是否回文java

java 订阅