毕业设计报告网站开发,什么网站专门学做湖北菜,百度爱采购服务商查询,网站打开速度判断一个单链表是不是回文#xff0c;主要有三种方法#xff0c;不过如果要考虑空间复杂度的话#xff0c;就只有常用的一种方法了。
这种方法很考验一个人的细心以及编程能力~
前两种方法比较简单我就不祥述了~
主要讲一下最后一种方法#xff1a;直接上图了~下面附上code…
判断一个单链表是不是回文主要有三种方法不过如果要考虑空间复杂度的话就只有常用的一种方法了。
这种方法很考验一个人的细心以及编程能力~
前两种方法比较简单我就不祥述了~
主要讲一下最后一种方法直接上图了~下面附上code
public static class Node { public int value; public Node next; public Node(int data) { this.value data; } } public static void main(String args[]) { Node head new Node(1); head.next new Node(2); head.next.next new Node(3); head.next.next.next new Node(3); head.next.next.next.next new Node(2); head.next.next.next.next.next new Node(1); printLinkedList(head); isHuiWenList1(head); isHuiWenList2(head); isHuiWenList3(head); } /* 打印单链表 */ 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(); } /* * 需要额外空间复杂度On这种方法在笔试中比较推荐。 大概四路如下 新建一个堆栈把list里面的元素一个一个 push进入堆栈中全部都放进去以后 * pop出来与单链表中的元素取出来进行比较如果完全相等则说明是回文不然不是 */ public static boolean isHuiWenList1(Node head) { if (head null || head.next null) { return true; } StackNode st new StackNode(); Node cur head; /* 将元素压入堆栈 */ while (cur ! null) { st.push(cur); cur cur.next; } /* 判断单链表中的元素是否与堆栈pop出来的元素相等 */ while (head ! null) { if (head.value ! st.pop().value) { System.out.println(false); return false; } else { head head.next; } } System.out.println(true); return true; } /* * 这种方法其实不怎么推荐虽然它额外空间复杂度是On/2但是编程相对来说有点难度不过这里涉及到一种常用的思想 * 定义一个指针slow和fastslow一次走一步fast一次走两步同时走当fast走完全程的时候slow刚好就在中点。 * 其他思想与方法一类似也是定义一个堆栈把单链表的元素放进去再把它pop出来进行比较。 */ public static boolean isHuiWenList2(Node head) { Node fast head; Node slow head; if (head null || head.next null) { return true; } /* 从这里开始走一个走一步一个走两步 */ if (fast.next ! null fast.next.next ! null) { fast fast.next.next; slow slow.next; } /* 下面的slow此时是中点 */ StackNode st new StackNode(); while (slow ! null) { st.push(slow); slow slow.next; } while (st.size() ! 0) { if (st.pop().value ! head.value) { System.out.println(false); return false; } else { head head.next; } } System.out.println(true); return true; } /* * 下面这种方法空间复杂度为o1适合于在笔试中使用很考验编程能力主要是在逆序那里很容易出错 不过一旦理解了这种思想逆序就不难理解了 */ public static boolean isHuiWenList3(Node head) { if (head null || head.next null) { System.out.println(true); return true; } /* 找中点位置也是通过两个指针来实现 */ Node slow head; Node fast head; while (fast.next ! null fast.next.next ! null) { slow slow.next; fast fast.next.next; } /* 将中点右边的单链表进行逆序 */ Node n3 null; fast slow.next; slow.next null; while (fast ! null) { n3 fast.next; fast.next slow; slow fast; fast n3; } /* 比较中点左边的元素和中点右边的元素是否相等也即判断是否为回文 */ n3 slow; fast head; boolean res true; while (slow ! null fast ! null) { if (slow.value ! fast.value) { res false; break; } slow slow.next; fast fast.next; } /* 将中点右边逆序的部分恢复过来其实这里我也不太懂为什么要恢复过来欢迎各位大神能来解答一下 */ slow n3.next; n3.next null; while (slow ! null) { fast slow.next; slow.next n3; n3 slow; slow fast; } System.out.println(res); return res; }
