判断单链表的值是否是回文结构
判断单链表的值是否是回文结构
writeademo 发表于9个月前
判断单链表的值是否是回文结构
  • 发表于 9个月前
  • 阅读 24
  • 收藏 0
  • 点赞 0
  • 评论 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));

 }
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 20
博文 428
码字总数 163509
×
writeademo
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: