leetcode 234.判斷鏈表是否為回文
題目描述
給定一個(gè)單鏈表，判斷它是否是回文。
示例
輸入: 1->2
輸出: false
輸入: 1->2->2->1
輸出: true
解法思路
判斷鏈表是否為回文，可以通過翻轉(zhuǎn)鏈表后半部分并比較兩半部分是否相同來實(shí)現(xiàn)。具體步驟如下：文章來源：http://www.zghlxwxcb.cn/news/detail-804403.html
- 使用快慢指針找到鏈表的中間節(jié)點(diǎn)。
- 翻轉(zhuǎn)鏈表的后半部分。
- 比較前半部分和翻轉(zhuǎn)后的后半部分是否相同。
代碼實(shí)現(xiàn)
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 將中間節(jié)點(diǎn)歸屬到前半部分
if (fast != null) {
slow = slow.next;
}
slow = reverseList(slow);
fast = head;
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)，其中 n 為鏈表的長(zhǎng)度。需要遍歷鏈表的一半來翻轉(zhuǎn)后半部分，然后再進(jìn)行比較。
- 空間復(fù)雜度：O(1)，只需要常數(shù)級(jí)別的額外空間。
希望這篇博客對(duì)你有幫助。如有任何疑問或建議，歡迎留言交流。文章來源地址http://www.zghlxwxcb.cn/news/detail-804403.html
到了這里，關(guān)于leetcode 234.判斷鏈表是否為回文的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
