文档章节

判断单链表的值是否是回文结构

writeademo
 writeademo
发布于 2017/08/12 10:44
字数 657
阅读 28
收藏 0

package com.javause.Algorithm.isPalindrome;

import java.util.Stack;

import org.junit.Test;

/**
 *
 * 一个链表是否是回文结构
 *
 */
public class ReturnStruct {
 class Node {
  public int value;
  public Node next;

  public Node(int data) {
   this.value = data;
  }
 }

 /**
  * 方法一:将链表节点依次入栈,入栈完成后,依次出栈,如果可以和原来的链表值对上,那就是回文结构,逆序之后,值相同
  *
  */
 public boolean isPalindromel(Node head) {
  Stack<Node> stack = new Stack<Node>();
  Node cur = head;
  while (cur != null) {
   stack.push(cur);
   cur = cur.next;
  }
  while (head != null) {
   if (head.value != stack.pop().value) {
    return false;
   }
   head = head.next;
  }
  return true;

 }

 /**
  * 方法二:并不是将所有节点入栈,压入一半节点即可,如果长度为N,N为 偶数,前N/2的节点叫左边区,后N/2的节点叫右半区
  * N为奇数,忽略处于最中间的节点,还是前N/2的节点叫左半区,后N/2的节点 叫右半区。
  * 把右边部分压入栈中,压入完成后,检查栈顶到栈底的值出现顺序是否和 链表左边的值相互对应
  *
  */
 public boolean isPalindrome2(Node head) {
  if (head == null || head.next == null) {
   return true;
  }
  Node right = head.next;
  Node cur = head;
  while (cur.next != null && cur.next.next != null) {
   right = right.next;
   cur = cur.next.next;
  }

  Stack<Node> stack = new Stack<Node>();
  while (right != null) {
   stack.push(right);
   right = right.next;
  }
  while (!stack.isEmpty()) {
   if (head.value != stack.pop().value) {
    return false;
   }
   head = head.next;
  }
  return true;
 }

 /**
  * 方法三:右半区反转,指向中间节点 将左边区第一个节点记为leftStart,右半区反转后第一个节点记为rightStart
  * 1.leftStart和rightStart同时向中间节点移动,移动每一步都比较leftStart和
  * rightStart的值,看是否一样,如果都一样,说明为回文结构 2.不管最后是不是回文,都要把链表恢复成原来的结构 3.恢复完成后,返回检查结果
  *
  */
 public boolean isPalindrome3(Node head) {
  if (head == null || head.next == null) {
   return true;
  }
  Node n1 = head;
  Node n2 = head;
  while (n2.next != null && n2.next.next != null) // 查找中间节点
  {
   n1 = n1.next; // 中部n1
   n2 = n2.next.next; // n2尾部
  }
  n2 = n1.next; // n2,右边第一个节点
  n1.next = null;// 将中间节点指针断开
  Node n3 = null;
  while (n2 != null) { // 右半区反转
   n3 = n2.next;// n3保存下一个节点
   n2.next = n1; // n2指向中间节点
   n1 = n2; // n1移动
   n2 = n3;// n2移动
  }

  n3 = n1;// n3->保存最后一个节点
  n2 = head;// n2->左边第一个节点

  boolean res = true;
  while (n1 != null && n2 != null) {// 检查回文
   if (n1.value != n2.value) {
    res = false;
    break;
   }
   n1 = n1.next;
   n2 = n2.next;
  }
  n1 = n3.next;
  n3.next = null;
  while (n1 != null) {// 恢复列表
   n2 = n1.next;
   n1.next = n3;
   n3 = n1;
   n1 = n2;
  }
  return res;
 }

 @Test
 public void test() {
  Node node1 = new Node(1);
  Node node2 = new Node(2);
  Node node3 = new Node(2);
  Node node4 = new Node(1);
  Node node5 = new Node(1);

  node1.next = node2;
  node2.next = node3;
  node3.next = node4;
  node4.next = node5;

  System.out.println(isPalindromel(node1));

  System.out.println(isPalindrome2(node1));

  System.out.println(isPalindrome3(node1));

 }
}

© 著作权归作者所有

共有 人打赏支持
writeademo
粉丝 25
博文 559
码字总数 205127
作品 0
东城
私信 提问
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0
LeetCode算法题-Palindrome Linked List(Java实现)

这是悦乐书的第196次更新,第202篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第58题(顺位题号是234)。给出一个单链表,确定它是否是回文。例如: 输入:1-> 2 输出:fal...

小川94
12/09
0
0
判断一个链表是否为回文结构。(时间复杂度要求O(n),空间复杂度要求O(1))

题目要求: 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度...

shs0708
2016/05/03
51
0
LeetCode基础算法-链表

# LeetCode基础算法-链表 LeetCode 链表 1. 删除链表中的节点 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 解题思路: 使用赋值取代法来实...

24K男
09/10
0
0
java简单算法总结

1、翻转字符串 function reverseString(str) { }reverseString("hello"); 2、阶乘算法 public static int factorialize(int num) { } else { } } public static void main(String[] args......

晚天吹凉风
2017/12/18
4
0

没有更多内容

加载失败,请刷新页面

加载更多

FTP 协议 1.0

自己制作的FTP协议:

Explorer0
21分钟前
1
0
Android 通过DrawableInflater加载自定义Drawable

一、Drawable 在Android系统张,图形图像的绘制需要在画布上进行操作和处理,但是绘制需要了解很多细节以及可能要进行一些复杂的处理,因此系统提供了一个被称之为Drawable的类来进行绘制处理...

IamOkay
33分钟前
1
0
灵活无处安放,所以选择流浪....《漆黑的空间》& 《灰色轨迹》

灵活无处安放,所以选择流浪....《漆黑的空间》& 《灰色轨迹》

yizhichao
39分钟前
1
0
Kafka+Flink 实现准实时异常检测系统

1.背景介绍 异常检测可以定义为“基于行动者(人或机器)的行为是否正常作出决策”,这项技术可以应用于非常多的行业中,比如金融场景中做交易检测、贷款检测;工业场景中做生产线预警;安防...

架构师springboot
今天
7
0
DecimalFormat 类基本使用

/* * DecimalFormat 类主要靠 # 和 0 两种占位符号来指定数字长度 * 0 表示如果位数不足则以 0 填充 * # 表示只要有可能就把数字拉上这个位置 * */ public static void main(String[] args){...

嘴角轻扬30
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部