這是我對問題的嘗試解決方案。 public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode hare = head; ListNode tort = head; while(hare!=null && hare.next!=null) { //System.out.print("Hare "+ hare.val +"tort "+tort.val); hare = hare.next.next; tort = tort.next; } //Tort is the middle of the list reverseLL(tort); ListNode tmp = tort; printList(tmp); while(tort!=null) { if(head.val!=tort.val) return false; head = head.next; tort = tort.next; continue; } return true;}private ListNode reverseLL(ListNode head) { if(head == null || head.next == null) { return head; } ListNode nextElem = head.next; //System.out.println("Processing "+head.val); head.next = null; ListNode rev = reverseLL(nextElem); nextElem.next = head; return rev;} private void printList(ListNode head){ while(head!=null){ System.out.println("[" +head.val + "]"); head = head.next; } }但我注意到一些我無法弄清楚的非常奇怪的事情。tort當(dāng)前結(jié)束于鏈表的中間。然而，從頭到尾的逆轉(zhuǎn)tort似乎將侵權(quán)行為與鏈表的其余部分?jǐn)嚅_。例如，如果輸入是 1->2->3->4，tort 最終是 3，但是在從 tort 反轉(zhuǎn)它之后打印列表只打印 3，即。3 與列表的其余部分?jǐn)嚅_連接。我已經(jīng)reverseLL單獨測試過它并且它可以工作，但是當(dāng)它作為 isPalindrome 方法的一部分應(yīng)用時。知道我可能缺少什么嗎？
2 回答
動漫人物
TA貢獻(xiàn)1815條經(jīng)驗 獲得超10個贊
似乎您想檢查回文就位，但您沒有說明這樣的要求，所以我提出了一種更直接的算法：
初始化堆棧
遍歷列表并將每個元素壓入棧頂
直到棧不為空：
彈出棧頂
將彈出的元素與列表的頭部進(jìn)行比較
如果不相等，返回
false彈出另一個元素，在列表中向前移動一個元素
返回
true
這是一個帶有泛型的 Java 實現(xiàn)：
public <T> boolean isPalindrome(ListNode<T> head) {
Stack<ListNode<T>> stack = new Stack<>();
ListNode<T> x = head;
while(x != null) {
stack.push(x);
x = x.next;
}
while(!stack.isEmpty()) {
ListNode<T> el = stack.pop();
if(el.t != head.t) return false;
head = head.next;
}
return true;
}
該算法在時間上為 O(n)，在空間上為 O(n)。
qq_笑_17
TA貢獻(xiàn)1818條經(jīng)驗 獲得超7個贊
在第一個 while 循環(huán)中找到鏈表的中間時，為什么不維護(hù)一個指向 tort 之前節(jié)點的指針：
ListNode prev_tort = head;
while(hare!=null && hare.next!=null) {
//System.out.print("Hare "+ hare.val +"tort "+tort.val);
hare = hare.next.next;
prev_tort = tort;
tort = tort.next;
}
現(xiàn)在，當(dāng)元素數(shù)為偶數(shù)時，hare 將為 NULL。因此，對于奇數(shù)情況，跳過中間節(jié)點：
if(hare != NULL){
tort = tort.next;
prev_tort = prev_tort.next;
}
tort = reverseLL(tort);
prev_tort.next = tort; // only to ensure list is connected
然后是您的比較代碼。
此外，在 reverseLL() 函數(shù)中：
ListNode rev = reverseLL(nextElem);
head.next.next = head;
head.next = NULL;
return rev;
如果我理解正確，您正在嘗試通過反轉(zhuǎn)后半部分來檢查列表是否為回文。在那種情況下，對于輸入 1->2->3->4，在反轉(zhuǎn)下半場后不應(yīng)該 tort 指向 4 嗎？這就是上面的代碼所做的（列表將是：1->2->4->3）。
添加回答
舉報
0/150
提交
取消