文档章节

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

writeademo
 writeademo
发布于 2017/08/12 10:44
字数 657
阅读 27
收藏 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
粉丝 24
博文 534
码字总数 191198
作品 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
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
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

没有更多内容

加载失败,请刷新页面

加载更多

Vue重要知识小结

vue sync修饰 (1)双向数据绑定,父子组件之间信息的交互 1⃣️在自组件中使用this.emmit('toFather'),子组件产生一个tofather事件,然后在父组件中通过@进行监听,那么可以实现通信过程 2⃣...

peakedness丶
47分钟前
1
0
1024我们的码农节-向自己致敬!

一、blog主有话要说 作为(真正)入赘程序届的第一年, 对明天的1024码农节有很多话想说.比如: 给各位辛苦大佬们讲几个咱们程序届段子 给自己立一个flag, 明年的1024争取少掉点甚至不掉头发! ...

Ala6
49分钟前
15
0
solr使用规范

0. 目的 规范solr设计、用法,避免bug,提高性能 1. 设计规范 solr的用途是查询,不是存储,建议查询结果尽量都为id主键,而后再拿该id主键到缓存或者db中再查询相关信息,例如:请勿将经销商...

andersChow
今天
1
0
11-《深度拆解JVM》之Java对象的内存布局

一、问题引入 在 Java 程序中,我们拥有多种新建对象的方式。除了最为常见的 new 语句之外,我们还可以通过反射机制、Object.clone 方法、反序列化以及 Unsafe.allocateInstance 方法来新建对...

飞鱼说编程
今天
1
0
Windows Install Docker

win7、win8 win7、win8 等需要利用 docker toolbox 来安装,国内可以使用阿里云的镜像来下载,下载地址:http://mirrors.aliyun.com/docker-toolbox/windows/docker-toolbox/ docker toolbox...

linuxprobe16
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部