-
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; }
更多相关内容 -
判断链表是否回文 Java
2020-05-28 11:20:48比如链表要从中间节点那里开始反转 找到的中间节点是 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实现判断是否为回文链表
2021-12-10 16:08:20Java实现回文链表判断判断是否为回文链表
之前做过判断是否为回文字符串的题目,用到的方法有,双指针,即一个从开始走,一个从末尾走,判断两者是否相等即可,当然其中需要注意的一个问题便是,要将大写字母都转化为小写字母
而单向链表不同于数组结构,无法直接从后向前,于是本人进行了如下尝试:
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.翻转后一半链表,与前一半链表进行比较
由于上述方法的失败,不得不考虑新的方法,其实我们不需要翻转整个链表,我们只需要翻转后一半链表,然后与前半部分链表进行比较即可。
问题转化如下:- 获得后半部分链表
可以使用快慢指针,快指针走两格,慢指针走一格,那么当快指针为空,或者快指针下一个为空时,慢指针就走到一半了,当然还涉及一个奇数偶数个结点的问题,如果是奇数个结点,那么慢指针应该继续向后走一格。代码如下:
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.总结
针对链表的回文判断,我觉很需要掌握快慢指针的运用,同时如何获得后一半的链表的思想,也是我们应该掌握的,此类方法在后续的学习中应当常用。全文手码,如有写的不好的,不对的地方希望大家批评指正,共同进步。
- 获得后半部分链表
-
三种方法判断链表是不是回文链表(java实现)
2020-11-04 20:55:29将链表节点依次入栈,因为栈先进后出的特性,当链表节点全部入栈后,栈中就保存了原链表节点的逆序排列,然后将栈顶节点依次出栈并顺序与链表节点进行比较,如果在比较过程中发现节点的值不同,说明不是回文链表 ...方法一:
最简单也最容易想到的方法,采用栈的数据结构,将链表节点依次入栈,因为栈先进后出的特性,当链表节点全部入栈后,栈中就保存了原链表节点的逆序排列,然后将栈顶节点依次出栈并顺序与链表节点进行比较,如果在比较过程中发现节点的值不同,说明不是回文链表【代码实现】
//首先给出节点类的定义 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)详细讲解
2022-01-05 11:03:48牛客网判断是否是回文链表(java)详细讲解 -
判断链表是不是回文结构
2021-12-10 20:21:07啥是回文结构:一个链表正向看和反向看都是一样的。 例如:1 --> 2 --> 2 --> 1,1 --> 2 --> 3 --> 2 --> 1这样的链表就具有回文结构。 1、额外空间复杂度为O(1)的写法: (1)找到此链表的... -
判断单链表是否为回文链表(Java)
2021-11-22 23:16:16判断单链表是否为回文链表 (牛客网—牛客题霸算法篇—NC96) 题目描述 给定一个链表,请判断该链表是否为回文结构。 回文是指该字符串正序逆序完全一致。 思路 Java实现 方法一:遍历 定义三个指针,分别为left、... -
判断链表是否为回文链表
2022-02-03 12:54:01import 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 ... -
Java判断该链表是否为回文结构
2021-01-15 01:45:03给定一个链表,请判断该链表是否为回文结构。 示例1 输入 [1,2,2,1] 返回值 true 对于一个回文链表可以发现,当指针节点在对其进行遍历时,走到中间位置就等同于从中间倒着往前走 如 1->2->3->2-&... -
三种方法判断链表是否为回文结构
2021-10-21 22:56:20方法三:利用快慢指针,找出链表中点位置,将链表后半部分翻转,依次比较两链表值,判断是否是回文结构后将翻转的链表还原。 package class04P; import java.util.Stack; public class Code04P_IsPalindromeList ... -
单链表练习题:判断链表是不是回文链表
2020-07-09 21:22:00思路:找到链表的中间节点,然后逆置后半段,再从两边比较对应位置是否值域相等。 代码: public boolean chkPalindrome(){ if(head==null){ return false; } if(head.next==null){ return true; } Node fast=head... -
判断链表是不是回文链表
2020-06-26 18:39:18* 判断链表是不是回文链表 */ public class IsPalindrome { //先找到链表的中间位置分开,然后把后半部分反转,遍历作比较,遇到不等就返回false public static boolean isPalindrome(ListNode head){ if(head... -
链表回文判断(基于链表反转)—Java实现
2021-03-15 04:18:18如果有链表反转的基础,实现链表回文判断就简单的多,如果对反转链表不熟悉,可以参考这篇博客。思路很简单,先找到链表的中间Node,采用的快慢指针法。慢指针一次走一步,快指针一次走两步,当快指针触底的时候,慢... -
判断链表是否回文(空间复杂度为O(1))
2021-11-08 11:03:18判断链表是否回文(空间复杂度为O(1)): 用到的有:快慢指针,链表翻转 代码: public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } Node n1 = ... -
第十一题:判断一个链表是否为回文结构(Java实现)
2019-01-10 22:09:51给定一个链表的头结点是head,请判断该链表是否为回文结构 例如: 1->2->1,返回true 1->2->2->1,返回true 1->2->3,返回false 分析: 在链表问题中,... -
java判断链表是否为回文结构
2021-01-03 14:22:15度为O(1)的算法,判断其是否为回文结构。给定一个链表的头 指针A,请返回一个bool值,代表其是否为回文结构。保证链 表长度小于等于900。 测试样例: 1->2->2->1 返回:true 问题解析 找到中间节点,然后... -
JAVA链表中的回文链表结构
2022-04-02 19:05:03作为一个java初学者,最近遇到了回文链表结构这个难题,经过一番学习总算搞清楚个大概。 先来说一下什么是回文链表,会问链表在我们生活中经常能够遇到。会问链表的结构就是 例如:1->2->3->2->1。... -
判断链表是是否是回文
2017-10-25 12:02:27* 判断一个链表是是否是回文结构 * 进阶:如果链表的长度为N,时间复杂度达到O(N),额外的空间复杂度是O(1)。 * @author lhs94 * @date 2017-10-24 */ public class JudgePalindromel { public ... -
判断一个链表是否回文--JAVA
2019-05-18 16:45:13判断一个链表是否回文 public class Nowcoder { public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public clas... -
Java判断链表的回文结构
2021-03-27 15:26:16给定一个链表,请判断该链表是否为回文结构。 点此查看字符串的回文结构 以下是本篇文章正文内容,下面案例可供参考 解题思路 1. 找中间结点位置 定义两个快慢结点,快的两个两个跑,慢的一个一个跑,当快的跑完... -
判断一个链表是否为回文链表的三种思路及JAVA代码实现
2020-08-10 14:24:36//合并两个有序链表 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:leetcode.com,algoexper
2021-07-01 00:53:27判断链表是否为回文链表 leetcode JAVA-coding-interview-Balazs 帮助: 这个 repo 包含大约 300 个 Leetcode.com 和 85 个 Algoexpert.io 问题以及使用 Swift 和 Python 的解决方案 这个 repo 包含我用Java和Python... -
LeetCode 283. Java判断一个链表是否为回文链表
2021-05-13 20:03:27判断一个链表是否为回文链表 请判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true //O(n)空间和时间复杂度 class Solution { public ... -
判断一个链表是否为回文结构-Java:解法三
2022-05-01 00:01:30分享一个大牛的人工智能教程。零基础!通俗易懂!... * 判断一个链表是否为回文结构。 * * 思路: * 不用栈和其他数据结构,只用有限几个变量。 * * @author Created by LiveEveryDay */ publi -
判断链表是否为回文结构
2022-06-10 20:38:52链表回文结构的判断 -
Java判断链表是否具有回文结构
2019-08-03 15:56:06给定一个链表的头指针,返回一个 bool 值,true 代表其为回文结构,false 代表不是。 思路: 1.先找到中间结点,然后以中间结点为头节点,逆置链表后半部分 2.然后遍历两个链表 当两个链表对应结点的值都相等时,... -
简单算法 判断一个链表是否为回文结构(java)
2021-07-27 11:06:07简单算法 判断一个链表是否为回文结构(java) 描述 给定一个链表,请判断该链表是否为回文结构。 示例 输入: [1,2,2,1] 返回值: true 说明: 1->2->2->1 想法:先使用快慢结点找到中间结点,然后通过... -
判断输入的链表是否为回文链表
2022-06-06 16:23:57链表的回文判断,里面涉及到到一个反转链表的方法