此仓库存储的是数据结构与经典算法.zip

package _02分类算法._03链表; import java.util.Stack; /* 判断一个链表是否为回文结构(三种方式) 【题目】 给定一个链表的头节点head，请判断该链表是否为回文结构。 例如： 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。 进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1) 思路1:(空间复杂度n)将链表从头结点依次放到栈中,放完后,每次从栈中取出一个元素和链表比较,如果不相等返回false 都相等则返回true 思路2:一个快指针一个慢指针,找到链表的中点 */ public class _02判断链表是否为回文 { public static class Node { public int value; public Node next; public Node(int data) { this.value = data; } } //方法一:需要O(n)的额外空间 public static boolean isPalindrome1(Node head) { //创建一个栈对象 Stack<Node> stack = new Stack<Node>(); Node cur = head; //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/2的额外空间 public static boolean isPalindrome2(Node head) { //没有元素和只有一个元素时直接返回true if (head == null || head.next == null) { return true; } //定义一个快指针cur一个慢指针right,当cur走到头时right正好处在中间的位置(然后只将右半部分压入栈中,节约一半的空间) Node right = head.next; //慢指针提前一步123->3 1234->3 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; } //方法三:需要O(1)的额外空间 public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } Node n1 = head; //慢指针提前一步123->2 1234->2 Node n2 = head; while (n2.next != null && n2.next.next != null) { // find mid node n1 = n1.next; // n1 -> mid n2 = n2.next.next; // n2 -> end } n2 = n1.next; // n2 -> right part first node n1.next = null; // mid.next -> null Node n3 = null; while (n2 != null) { // right part convert n3 = n2.next; // n3 -> save next node n2.next = n1; // next of right node convert n1 = n2; // n1 move n2 = n3; // n2 move } n3 = n1; // n3 -> save last node n2 = head;// n2 -> left first node boolean res = true; while (n1 != null && n2 != null) { // check palindrome if (n1.value != n2.value) { res = false; break; } n1 = n1.next; // left to mid n2 = n2.next; // right to mid } n1 = n3.next; n3.next = null; while (n1 != null) { // recover list n2 = n1.next; n1.next = n3; n3 = n1; n1 = n2; } return res; } //打印列表元素的工具类 public static void printLinkedList(Node node) { System.out.print("Linked List: "); while (node != null) { System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { Node head = null; printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(2); head.next.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(2); head.next.next.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); } } //工具类-----工具类-------工具类------工具类------工具类---------工具类------------工具类-------------工具类-------工具类---