單鏈表迴文判斷
- 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; }
