久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

# Check if a singly linked list is palindrome - tags: [palindrome, linked_list] ### Source - [Function to check if a singly linked list is palindrome - GeeksforGeeks](http://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/) ~~~ Given a singly linked list of characters, write a function that returns true if the given list is palindrome, else false. ~~~ ### 題解1 - 使用輔助棧 根據(jù)棧的特性(FILO)，可以首先遍歷鏈表并入棧(最后訪問棧時則反過來了)，隨后再次遍歷鏈表并比較當(dāng)前節(jié)點(diǎn)和棧頂元素，若比較結(jié)果完全相同則為回文。 又根據(jù)回文的特性，實(shí)際上還可以只遍歷鏈表前半部分節(jié)點(diǎn)，再用棧中的元素和后半部分元素進(jìn)行比較，分鏈表節(jié)點(diǎn)個數(shù)為奇數(shù)或者偶數(shù)考慮即可。由于鏈表長度未知，因此可以考慮使用快慢指針求得。 ### Java ~~~ /** * Definition for singly-linked list. */ class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { public static boolean isPalindrome(ListNode head) { ListNode fast = head; ListNode slow = head; Stack<Integer> stack = new Stack<Integer>(); // push node before mid while (fast != null && fast.next != null) { stack.push(slow.val); slow = slow.next; fast = fast.next.next; } // skip mid node for odd size if (fast != null) { slow = slow.next; } while (slow != null) { int top = stack.pop(); // compare top with slow.val if (top != slow.val) { return false; } slow = slow.next; } return true; } public static void main (String[] args) { int len = 9; ListNode head = new ListNode(0); ListNode node = head; for (int i = 1; i < 9; i++) { int temp = (i >= len / 2) ? (len - i - 1) : i; node.next = new ListNode(temp); node = node.next; } System.out.println(isPalindrome(head)); } } ~~~ ### 源碼分析 注意區(qū)分好鏈表中個數(shù)為奇數(shù)還是偶數(shù)就好了，舉幾個簡單例子輔助分析。 ### 復(fù)雜度分析 使用了棧作為輔助空間，空間復(fù)雜度為 O(12n)O(\frac{1}{2}n)O(21n), 分別遍歷鏈表的前半部分和后半部分，時間復(fù)雜度為 O(n)O(n)O(n). ### 題解2 - 原地翻轉(zhuǎn) 題解 1 的解法使用了輔助空間，在可以改變原來的鏈表的基礎(chǔ)上，可使用原地翻轉(zhuǎn)，思路為翻轉(zhuǎn)前半部分，然后迭代比較。具體可分為以下四個步驟。 1. 找中點(diǎn)。 1. 翻轉(zhuǎn)鏈表的后半部分。 1. 逐個比較前后部分節(jié)點(diǎn)值。 1. 鏈表復(fù)原，翻轉(zhuǎn)后半部分鏈表。 ### Java ~~~ /** * Definition for singly-linked list. */ class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { public static boolean isPalindrome(ListNode head) { ListNode fast = head; ListNode slow = head; // push node before mid while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // skip mid node for odd number if (fast != null) { slow = slow.next; } ListNode rightHead = reverse(slow); ListNode rCurr = rightHead; ListNode lCurr = head; while (rCurr != null) { if (rCurr.val != lCurr.val) { return false; } lCurr = lCurr.next; rCurr = rCurr.next; } // recover list rightHead = reverse(rightHead); return true; } public static ListNode reverse (ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } public static void main (String[] args) { int len = 9; ListNode head = new ListNode(0); ListNode node = head; for (int i = 1; i < 9; i++) { int temp = (i >= len / 2) ? (len - i - 1) : i; node.next = new ListNode(temp); node = node.next; } System.out.println(isPalindrome(head)); } } ~~~ ### 源碼分析 連續(xù)翻轉(zhuǎn)兩次右半部分鏈表即可復(fù)原原鏈表，將一些功能模塊如翻轉(zhuǎn)等盡量模塊化。 ### 復(fù)雜度分析 遍歷鏈表若干次，時間復(fù)雜度近似為 O(n)O(n)O(n), 使用了幾個臨時遍歷，空間復(fù)雜度為 O(1)O(1)O(1). ### 題解3 - 遞歸 遞歸需要兩個重要條件，遞歸步的建立和遞歸終止條件。對于回文比較，理所當(dāng)然應(yīng)該遞歸比較第 i 個節(jié)點(diǎn)和第 n-i 個節(jié)點(diǎn)，那么問題來了，如何構(gòu)建這個遞歸步？大致可以猜想出來遞歸的傳入?yún)?shù)應(yīng)該包含兩個節(jié)點(diǎn)，用以指代第 i 個節(jié)點(diǎn)和第 n-i 個節(jié)點(diǎn)。返回參數(shù)應(yīng)該包含布爾值(用以提前返回不是回文的情況)和左半部分節(jié)點(diǎn)的下一個節(jié)點(diǎn)(用以和右半部分的節(jié)點(diǎn)進(jìn)行比較)。由于需要返回兩個值，在 Java 中需要使用自定義類進(jìn)行封裝，C/C++ 中則可以使用指針改變在**遞歸調(diào)用后**進(jìn)行比較時節(jié)點(diǎn)的值。 ### Java ~~~ /** * Definition for singly-linked list. */ class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { private class Result { ListNode node; boolean isp; Result(ListNode aNode, boolean ret) { isp = ret; node = aNode; } } public Result helper(ListNode left, ListNode right) { Result result = new Result(left, true); if (right == null) return result; result = helper(left, right.next); boolean isp = (right.val == result.node.val); if (!isp) { result.isp = false; } result.node = result.node.next; return result; } public boolean isPalindrome(ListNode head) { Result ret = helper(head, head); return ret.isp; } public static void main (String[] args) { int len = 9; ListNode head = new ListNode(0); ListNode node = head; for (int i = 1; i < 9; i++) { int temp = (i >= len / 2) ? (len - i - 1) : i; node.next = new ListNode(temp); node = node.next; } Solution ret = new Solution(); System.out.println(ret.isPalindrome(head)); } } ~~~ ### 源碼分析 核心代碼為返回 Result 復(fù)合數(shù)據(jù)類型部分，返回 result 后在返回最終結(jié)果之前需要執(zhí)行`result.node = result.node.next`, 左半部分節(jié)點(diǎn)往后遞推，用以返回給上層回調(diào)用。 ### 復(fù)雜度分析 遞歸調(diào)用 n 層，時間復(fù)雜度近似為 O(n)O(n)O(n), 使用了幾個臨時變量，空間復(fù)雜度為 O(1)O(1)O(1). ### Reference - [Function to check if a singly linked list is palindrome - GeeksforGeeks](http://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/) - [回文判斷 | The-Art-Of-Programming-By-July/01.04.md](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.04.md) - [ctci/QuestionB.java at master · gaylemcd/ctci](https://github.com/gaylemcd/ctci/blob/master/java/Chapter%202/Question2_7/QuestionB.java)