wordpress主題king,seo優(yōu)化檢測,中山最好的網(wǎng)站建設(shè)公司哪家好,幫助網(wǎng)站源碼問題描述 給定一個(gè)單鏈表的頭節(jié)點(diǎn) head#xff0c;判斷該鏈表是否為回文鏈表。如果是#xff0c;返回 true#xff1b;否則#xff0c;返回 false。 示例 #xff1a; 輸入: head [1,2,2,1] 輸出: true輸入: head [1,2] 輸出: false 進(jìn)階#xff1a; 你能否用 O(n)…問題描述給定一個(gè)單鏈表的頭節(jié)點(diǎn)head判斷該鏈表是否為回文鏈表。如果是返回true否則返回false。示例 輸入: head [1,2,2,1] 輸出: true輸入: head [1,2] 輸出: false進(jìn)階你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題解法一反轉(zhuǎn)后半部分鏈表最優(yōu)解這是面試中最常考的方法時(shí)間復(fù)雜度 O(n)空間復(fù)雜度 O(1)。算法步驟使用快慢指針找到鏈表的中間節(jié)點(diǎn)反轉(zhuǎn)鏈表的后半部分比較前半部分和反轉(zhuǎn)后的后半部分恢復(fù)鏈表可選代碼實(shí)現(xiàn)class Solution { public boolean isPalindrome(ListNode head) { if(headnull||head.nextnull){ return true; } ListNode midFind_mid(head); ListNode head2reverse_List(mid); while(head2!null){ if(head.val!head2.val){ return false; } headhead.next; head2head2.next; } return true; } private ListNode reverse_List(ListNode head){//反轉(zhuǎn)鏈表 ListNode prenull; ListNode curhead; while(cur!null){ ListNode Tempcur.next; cur.nextpre; precur; curTemp; } return pre; } private ListNode Find_mid(ListNode head){//找到中間節(jié)點(diǎn) ListNode slowhead; ListNode fasthead; while(fast!nullfast.next ! null){ slowslow.next; fastfast.next.next; } return slow; } }關(guān)鍵點(diǎn)分析快慢指針找中點(diǎn)慢指針每次走一步快指針每次走兩步當(dāng)快指針到達(dá)末尾時(shí)慢指針正好在中點(diǎn)對于奇數(shù)長度鏈表慢指針停在中間節(jié)點(diǎn)對于偶數(shù)長度鏈表慢指針停在中間兩個(gè)節(jié)點(diǎn)的第二個(gè)反轉(zhuǎn)鏈表使用三個(gè)指針pre、curr、Tempcur指向prepre往前移cur往前移每次迭代將當(dāng)前節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度與空間復(fù)雜度時(shí)間復(fù)雜度O(n)找中點(diǎn)O(n/2) ≈ O(n)反轉(zhuǎn)后半部分O(n/2) ≈ O(n)比較兩部分O(n/2) ≈ O(n)總時(shí)間O(n)空間復(fù)雜度O(1)只使用了常數(shù)級(jí)別的額外空間解法二使用棧思路利用棧的后進(jìn)先出特性將鏈表元素入棧然后依次出棧與鏈表比較。代碼實(shí)現(xiàn)javaclass Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } StackInteger stack new Stack(); ListNode current head; // 將鏈表值壓入棧中 while (current ! null) { stack.push(current.val); current current.next; } // 比較棧頂元素和鏈表當(dāng)前值 current head; while (current ! null) { if (current.val ! stack.pop()) { return false; } current current.next; } return true; } }復(fù)雜度分析時(shí)間復(fù)雜度O(n)需要遍歷鏈表兩次空間復(fù)雜度O(n)需要額外棧空間解法三遞歸思路利用遞歸的調(diào)用棧從鏈表末尾開始比較。代碼實(shí)現(xiàn)javaclass Solution { private ListNode frontPointer; public boolean isPalindrome(ListNode head) { frontPointer head; return recursivelyCheck(head); } private boolean recursivelyCheck(ListNode currentNode) { if (currentNode ! null) { // 遞歸到鏈表末尾 if (!recursivelyCheck(currentNode.next)) { return false; } // 比較當(dāng)前節(jié)點(diǎn)值和前端指針的值 if (currentNode.val ! frontPointer.val) { return false; } // 前端指針向后移動(dòng) frontPointer frontPointer.next; } return true; } }復(fù)雜度分析時(shí)間復(fù)雜度O(n)需要遞歸遍歷整個(gè)鏈表空間復(fù)雜度O(n)遞歸調(diào)用棧的空間解法四復(fù)制到數(shù)組 雙指針?biāo)悸穼㈡湵碇祻?fù)制到數(shù)組中然后使用雙指針判斷數(shù)組是否為回文。代碼實(shí)現(xiàn)javaclass Solution { public boolean isPalindrome(ListNode head) { // 將鏈表值復(fù)制到數(shù)組中 ListInteger values new ArrayList(); ListNode current head; while (current ! null) { values.add(current.val); current current.next; } // 使用雙指針判斷數(shù)組是否為回文 int left 0; int right values.size() - 1; while (left right) { if (!values.get(left).equals(values.get(right))) { return false; } left; right--; } return true; } }復(fù)雜度分析時(shí)間復(fù)雜度O(n)復(fù)制到數(shù)組O(n)雙指針比較O(n/2) ≈ O(n)空間復(fù)雜度O(n)需要額外數(shù)組存儲(chǔ)鏈表值常見錯(cuò)誤與注意事項(xiàng)錯(cuò)誤1沒有處理奇偶長度差異java// 錯(cuò)誤示例沒有考慮奇偶長度差異 private ListNode findMiddle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null) { // 錯(cuò)誤應(yīng)該檢查fast.next slow slow.next; fast fast.next.next; } return slow; }修正javaprivate ListNode findMiddle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }錯(cuò)誤2反轉(zhuǎn)鏈表實(shí)現(xiàn)錯(cuò)誤修正javaprivate ListNode reverseList(ListNode head) { ListNode pre null; ListNode cur head; while (cur ! null) { ListNode temp cur.next; cur.next pre; pre cur; cur temp; } return pre; }擴(kuò)展如果要恢復(fù)鏈表怎么辦如果需要保持鏈表原樣可以在比較后再次反轉(zhuǎn)恢復(fù)javaclass Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) return true; // 找到中點(diǎn) ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 反轉(zhuǎn)后半部分 ListNode secondHalf reverseList(slow); // 比較 ListNode p1 head, p2 secondHalf; boolean result true; while (p2 ! null) { if (p1.val ! p2.val) { result false; break; } p1 p1.next; p2 p2.next; } // 恢復(fù)鏈表 reverseList(secondHalf); return result; } private ListNode reverseList(ListNode head) { ListNode prev null, curr head; while (curr ! null) { ListNode nextTemp curr.next; curr.next prev; prev curr; curr nextTemp; } return prev; } }總結(jié)方法時(shí)間復(fù)雜度空間復(fù)雜度優(yōu)點(diǎn)缺點(diǎn)反轉(zhuǎn)后半部分O(n)O(1)空間最優(yōu)滿足進(jìn)階要求修改了原鏈表結(jié)構(gòu)使用棧O(n)O(n)實(shí)現(xiàn)簡單不修改原鏈表需要額外空間遞歸O(n)O(n)代碼簡潔遞歸深度可能較大復(fù)制到數(shù)組O(n)O(n)實(shí)現(xiàn)簡單需要額外空間推薦使用反轉(zhuǎn)后半部分鏈表的方法因?yàn)榭臻g復(fù)雜度為 O(1)滿足進(jìn)階要求時(shí)間復(fù)雜度為 O(n)性能良好是面試中最?？嫉慕夥ㄏ嚓P(guān)題目反轉(zhuǎn)鏈表基礎(chǔ)中的基礎(chǔ)必須掌握鏈表的中間結(jié)點(diǎn)快慢指針的經(jīng)典應(yīng)用回文數(shù)字類似的回文判斷問題回文字符串字符串版本的回文判斷掌握這道題的關(guān)鍵在于理解快慢指針和鏈表反轉(zhuǎn)這兩個(gè)核心技巧這兩個(gè)技巧在鏈表相關(guān)題目中非常常見。