# 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 - 使用輔助棧 根據棧的特性(FILO)，可以首先遍歷鏈表并入棧(最后訪問棧時則反過來了)，隨后再次遍歷鏈表并比較當前節點和棧頂元素，若比較結果完全相同則為回文。 又根據回文的特性，實際上還可以只遍歷鏈表前半部分節點，再用棧中的元素和后半部分元素進行比較，分鏈表節點個數為奇數或者偶數考慮即可。由于鏈表長度未知，因此可以考慮使用快慢指針求得。 ### 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)); } } ~~~ ### 源碼分析 注意區分好鏈表中個數為奇數還是偶數就好了，舉幾個簡單例子輔助分析。 ### 復雜度分析 使用了棧作為輔助空間，空間復雜度為 O(12n)O(\frac{1}{2}n)O(21n), 分別遍歷鏈表的前半部分和后半部分，時間復雜度為 O(n)O(n)O(n). ### 題解2 - 原地翻轉 題解 1 的解法使用了輔助空間，在可以改變原來的鏈表的基礎上，可使用原地翻轉，思路為翻轉前半部分，然后迭代比較。具體可分為以下四個步驟。 1. 找中點。 1. 翻轉鏈表的后半部分。 1. 逐個比較前后部分節點值。 1. 鏈表復原，翻轉后半部分鏈表。 ### 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)); } } ~~~ ### 源碼分析 連續翻轉兩次右半部分鏈表即可復原原鏈表，將一些功能模塊如翻轉等盡量模塊化。 ### 復雜度分析 遍歷鏈表若干次，時間復雜度近似為 O(n)O(n)O(n), 使用了幾個臨時遍歷，空間復雜度為 O(1)O(1)O(1). ### 題解3 - 遞歸 遞歸需要兩個重要條件，遞歸步的建立和遞歸終止條件。對于回文比較，理所當然應該遞歸比較第 i 個節點和第 n-i 個節點，那么問題來了，如何構建這個遞歸步？大致可以猜想出來遞歸的傳入參數應該包含兩個節點，用以指代第 i 個節點和第 n-i 個節點。返回參數應該包含布爾值(用以提前返回不是回文的情況)和左半部分節點的下一個節點(用以和右半部分的節點進行比較)。由于需要返回兩個值，在 Java 中需要使用自定義類進行封裝，C/C++ 中則可以使用指針改變在**遞歸調用后**進行比較時節點的值。 ### 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 復合數據類型部分，返回 result 后在返回最終結果之前需要執行`result.node = result.node.next`, 左半部分節點往后遞推，用以返回給上層回調用。 ### 復雜度分析 遞歸調用 n 層，時間復雜度近似為 O(n)O(n)O(n), 使用了幾個臨時變量，空間復雜度為 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)