判断一个链表是否为回文结构
【题目】 给定一个链表的头节点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)
* 2、两个指针,一个快指针,一个慢指针,快指针每次走两步,慢指针每次走一步,当快指针走到末尾时,慢指针走到中点,
* 然后将慢指针后面的全部压入栈内,然后依次弹出和从头开始的元素进行比较(空间复杂度为n/2)
* 3、两个指针,一个快指针,一个慢指针,快指针每次走两步,慢指针每次走一步,当快指针走到末尾时,慢指针走到中点,
* 然后将慢指针右部分逆序(改指针),然后从两端开始判断是否相等(空间复杂度为1)
*/
public class 判断链表是否回文 { public static class Node{ public int value; public Node next; public Node(int data) { this.value = data; } } public static void printLinkedList(Node node) { while(node != null) { System.out.print(node.value+" "); node = node.next; } System.out.println(); } //空间复杂度为n public static boolean isp1(Node head) { Stack stack = new Stack(); 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/2 public static boolean isp2(Node head) { while(head == null || head.next == null) { return true; } Node slow = head.next; Node quick = head; while(quick.next != null && quick.next.next != null) { slow = slow.next; quick = quick.next.next; } Stack stack = new Stack(); while(slow != null) { stack.push(slow); slow = slow.next; } while(!stack.isEmpty()) { if(head.value != stack.pop().value) { return false; } head = head.next; } return true; } //空间复杂度为1 public static boolean isp3(Node head) { while(head == null || head.next == null) { return true; } Node n1 = head; Node n2 = head; while(n2.next != null && n2.next.next != null) { n1 = n1.next; //中点 n2 = n2.next.next; //结尾 } //逆序右半部分 n2 = n1.next; //右半部分第一个节点 head n1 = null; //pre Node n3 = null; //next while(n2 != null) { n3 = n2.next; n2.next = n1; n1 = n2; n2 = n3; } //判断是否回文 n3 = n1; n2 = head; 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; } public static void main(String[] args) { Node head = null; 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(isp1(head) + " | "); System.out.print(isp2(head) + " | "); System.out.println(isp3(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(isp1(head) + " | "); System.out.print(isp2(head) + " | "); System.out.println(isp3(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(isp1(head) + " | "); System.out.print(isp2(head) + " | "); System.out.println(isp3(head) + " | "); printLinkedList(head); System.out.println("========================="); } }