单链表回文判断
- 2020 年 1 月 23 日
- 筆記
判断一个单链表是否为回文链表目前有两种实现思路。一种是通过数组记录前半部分与后半部分依次比较，一种是找到链表中间结点，将左半部分反转与右半部分依次比较，下面详细介绍。
基于数组
用数组存储链表前半段的值，使用快慢指针法来进行截取。
public boolean isPalindromeByArray(Node node){ if (node == null) return false; Node fast = node; Node slow = node; if (node.next == null) return true; /** * 找到中间结点，同时用数组逆插左侧元素并保存。 * nodeList.add(0, slow.data); 在指定位置插入元素，原位置及之后的依次向右移动一位。 */ List<Integer> nodeList = new ArrayList<Integer>(); nodeList.add(0, slow.data); while (fast.next != null && fast.next.next != null ) { fast = fast.next.next; slow = slow.next; nodeList.add(0, slow.data); } if (fast.next != null){ // fast.next不为空，数据为偶数。 slow = slow.next; } Node curr = slow; int i = 0; while (null != curr){ if (curr.data != nodeList.get(i)){ return false; } curr = curr.next; i++; } return true; }
nodeList.add(0, slow.data);插入是比较耗时的，毕竟每次插入都需要将之前的依次向右移动一位。所以可以考虑用栈实现。
基于栈的回文判断
思路同基于数组的，但因为免去了保存新结点的右移操作，所以比使用数组保存左侧数据的方式高效一些。
/** * 基于栈比较是否为回文--半栈 * @param node * @return */ public boolean isPalindromeByStack(Node node){ if (node == null) return false; Node fast = node; Node slow = node; if (node.next == null) return true; /** * 找到中间结点，同时用栈保存左侧数据。 * */ Stack<Integer> nodeList = new Stack<Integer>(); nodeList.push(slow.data); // 1 2 3 while (fast.next != null && fast.next.next != null ) { fast = fast.next.next; slow = slow.next; nodeList.push(slow.data); // 1 2 3 } if (fast.next != null){ // fast.next不为空，数据为偶数。 slow = slow.next; } Node curr = slow; int i = 0; while (null != curr){ if (curr.data != nodeList.pop()){ return false; } curr = curr.next; i++; } return true; }
基于链表反转的回文判断
该方案的思路是：通过快慢指针获取中间结点，反转中间结点左侧部分，遍历并对比反转后左右两侧结点的数据判是否为回文。
只需要固定的若干个临时变量,不需要额外开辟空间
时间复杂度为O(n),空间复杂度为O(1)
该方式可以略作简化将反转左侧部分在查中间结点时同时完成。这里为了方便阅读，分开了查找中间结点和反转左侧结点的步骤，不再实现该优化。
/** * 不含逻辑头节点的回文链表判断 * 思路： * 遍历一遍链表,得到链表长度n,根据长度的奇偶,找到中间节点,将左半边的链表反转,然后从中间节点分两个方向向左右两边遍历,是否是回文; * * 对左半部分链表进行反转,还原为最初的链表（目前函数未实现左半部分链表还原） * * * 1 2 3 4 5 8 9 slow 4 fast 9 * 1 2 3 4 5 8 slow 3 fast 5 * @return */ public boolean isPalindrome(Node head){ if (head == null) return false; PrintUtill.println("开始执行找到中间节点"); Node fast = head; Node slow = head; if (fast.next == null){ System.out.println("只有一个元素"); return true; } /** * 快的一次走两步,慢的一次走一步那么最后快的结束了慢的走了一半 */ while (fast.next !=null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; } Node leftLink = null; Node rightLink = null; /** * 获取中间结点左右两部分，反转左侧部分。 * fast.next == null ：节点数目为奇数,且slow一定为为中间节点 * fast.next.next == null ：节点数目为偶数，slow、slow.next 均为中心结点 */ rightLink = slow.next; if (fast.next == null){ leftLink = inverseLinkListToEnd(slow).next; }else { leftLink = inverseLinkListToEnd(slow); } /** * 从此处开始同步向两边比较 */ return TFResult(leftLink, rightLink); } /** * 比较是否为回文 * @param left * @param right * @return */ public boolean TFResult(Node left, Node right){ while (left != null && right != null){ if (left.data != right.data){ return false; } left = left.next; right = right.next; } return true; } /** * 反转中间结点的左半部分，返回以end结点为头节点的链表。 * @param end * @return */ public Node inverseLinkListToEnd(Node end) { Node pre = null; Node cur = head; Node next = null; /** * 反转中间结点之前的结点 */ while (cur!=end){ next = cur.next; cur.next = pre; pre = cur; cur = next; } cur.next = pre; return cur; }
