文档章节

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

writeademo
 writeademo
发布于 2017/08/12 10:44
字数 657
阅读 25
收藏 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
粉丝 23
博文 486
码字总数 179522
作品 0
东城
《程序员代码面试指南》Python实现(个人读书笔记)

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

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

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

shs0708
2016/05/03
51
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
LeetCode:Valid Palindrome - 回文字符串

1、题目名称 Valid Palindrome(回文字符串) 2、题目地址 https://leetcode.com/problems/valid-palindrome/ 3、题目内容 英文:Given a string, determine if it is a palindrome, consid......

北风其凉
2015/08/05
0
0
编写函数,检查链表是否为回文

题解: 判断一个链表是不是回文的,这里要求O(n)时间复杂度和O(1)的空间时间复杂度,总共想了三种办法,三种办法都用到了两个指针,符合题目要求的只有最后一种。 第一种办法:用数组倒着...

一贱书生
2016/11/16
15
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

MySQL 乱七八糟的可重复读隔离级别实现

MySQL 乱七八糟的可重复读隔离级别实现 摘要: 原文可阅读 http://www.iocoder.cn/Fight/MySQL-messy-implementation-of-repeatable-read-isolation-levels 「shimohq」欢迎转载,保留摘要,谢...

DemonsI
59分钟前
2
0
Spring源码阅读——2

在阅读源码之前,先了解下Spring的整体架构: 1、Spring的整体架构 1. Ioc(控制反转) Spring核心模块实现了Ioc的功能,它将类与类之间的依赖从代码中脱离出来,用配置的方式进行依赖关系描...

叶枫啦啦
今天
1
0
jQuery.post() 函数格式详解

jquery的Post方法$.post() $.post是jquery自带的一个方法,使用前需要引入jquery.js 语法:$.post(url,data,callback,type); url(必须):发送请求的地址,String类型 data(可选):发送给后台的...

森火
今天
0
0
referer是什么意思?

看看下面这个回答(打不开网页可以把网址复制到搜索栏): https://zhidao.baidu.com/question/577842068.html

杉下
今天
1
0
使用U盘安装CentOS-解决U盘找不到源

1. 使用UltraISO制作CentOS安装盘 如果需要安装带界面的系统,为保证安装顺利,可选择Everything版本的ISO制作安装盘。 2. 在BIOS中选择使用U盘安装 系统启动后,进入安装选择界面,其中有三...

Houor
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部