Palindrome Linked List

    Example

    Given , return true

    Challenge

    Could you do it in O(n) time and O(1) space?

    根据栈的特性(FILO)，可以首先遍历链表并入栈(最后访问栈时则反过来了)，随后再次遍历链表并比较当前节点和栈顶元素，若比较结果完全相同则为回文。 又根据回文的特性，实际上还可以只遍历链表前半部分节点，再用栈中的元素和后半部分元素进行比较，分链表节点个数为奇数或者偶数考虑即可。由于链表长度未知，因此可以考虑使用快慢指针求得。

    Python

    源码分析

    注意， 在python code中， slow 和 fast pointer 分别指向head 和head.next。 这样指向的好处是：当linked－list 有奇数个数字的时候， 最终位置，slow会停在mid的位置， 而fast指向空。 当linked－list有偶数个node时， 最终位置，slow和slow.next为中间的两个元素， fast指向最后一个node。所以slow的最终位置总是mid 或者mid 偏左一点的位置。这样的位置非常方便分割linked－list，以及其他计算。推荐采用这种方法来寻找linked－list的mid位置。模版优势，请见solution2。

    Java

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. public class Solution {
    10.     /**
    11.      * @param head a ListNode
    12.      * @return a boolean
    13.      */
    14.     public boolean isPalindrome(ListNode head) {
    15.         if (head == null || head.next == null) return true;
    17.         Deque<Integer> stack = new ArrayDeque<Integer>();
    18.         // find middle
    19.         ListNode slow = head, fast = head;
    20.             stack.push(slow.val);
    21.             slow = slow.next;
    22.             fast = fast.next.next;
    23.         }
    25.         // skip mid node if the number of ListNode is odd
    26.         if (fast != null) slow = slow.next;
    28.         ListNode rCurr = slow;
    29.         while (rCurr != null) {
    30.             if (rCurr.val != stack.pop()) return false;
    31.             rCurr = rCurr.next;
    32.         }
    34.         return true;
    35.     }

    源码分析

    复杂度分析

    使用了栈作为辅助空间，空间复杂度为 O(\frac{1}{2}n), 分别遍历链表的前半部分和后半部分，时间复杂度为 O(n).

    题解 1 的解法使用了辅助空间，在可以改变原来的链表的基础上，可使用原地翻转，思路为翻转前半部分，然后迭代比较。具体可分为以下四个步骤。

    1. 找中点。
    2. 翻转链表的后半部分。
    3. 逐个比较前后部分节点值。
    4. 链表复原，翻转后半部分链表。

    源码分析

    对比Java code， 会发现，把slow 和fast pointer 放在head和head.next减少了对odd 或者even number的判断。因为slow总是在mid的位置或者mid偏左的位置上， 所以把mid assign 为slow.next总是对的。

    Java

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. public class Solution {
    10.     /**
    11.      * @param head a ListNode
    12.      * @return a boolean
    13.      */
    14.     public boolean isPalindrome(ListNode head) {
    15.         if (head == null || head.next == null) return true;
    17.         // find middle
    18.         ListNode slow = head, fast = head;
    19.         while (fast != null && fast.next != null) {
    20.             slow = slow.next;
    21.             fast = fast.next.next;
    22.         }
    24.         // skip mid node if the number of ListNode is odd
    25.         if (fast != null) slow = slow.next;
    27.         // reverse right part of List
    28.         ListNode lCurr = head, rCurr = rHead;
    29.         while (rCurr != null) {
    30.             if (rCurr.val != lCurr.val) {
    31.                 reverse(rHead);
    32.                 return false;
    33.             }
    34.             lCurr = lCurr.next;
    35.             rCurr = rCurr.next;
    37.         // recover right part of List
    38.         reverse(rHead);
    40.         return true;
    41.     }
    43.     private ListNode reverse(ListNode head) {
    44.         ListNode prev = null;
    45.         while (head != null) {
    46.             ListNode after = head.next;
    47.             head.next = prev;
    48.             prev = head;
    49.             head = after;
    50.         }
    52.         return prev;
    53.     }
    54. }

    C++

    源码分析

    连续翻转两次右半部分链表即可复原原链表，将一些功能模块如翻转等尽量模块化。

    复杂度分析

    递归需要两个重要条件，递归步的建立和递归终止条件。对于回文比较，理所当然应该递归比较第 i 个节点和第 n-i 个节点，那么问题来了，如何构建这个递归步？大致可以猜想出来递归的传入参数应该包含两个节点，用以指代第 i 个节点和第 n-i 个节点。返回参数应该包含布尔值(用以提前返回不是回文的情况)和左半部分节点的下一个节点(用以和右半部分的节点进行比较)。由于需要返回两个值，在 Java 中需要使用自定义类进行封装，C/C++ 中则可以使用指针改变在递归调用后进行比较时节点的值。

    1. class Solution:
    2.     def is_palindrome(self, head):
    3.         result = [head, True]
    4.         self.helper(head, result)
    5.         return result[1]
    7.     def helper(self, right, result):
    8.         if right:
    9.             self.helper(right.next, result)
    10.             is_pal =  result[0].val == right.val and result[1]
    11.             result = [result[0].next, is_pal]

    Java

    源码分析

    核心代码为如何在递归中推进左半部分节点而对右半部分使用栈的方式逆向获取节点。左半部分的推进需要借助辅助数据结构Result.

    复杂度分析

    递归调用 n 层，时间复杂度近似为 O(n), 使用了几个临时变量，空间复杂度为 O(1).

    Bonus - Fancy Python Solution

    1. class Solution:
    2.     def is_palindrome(self, head):
    3.         nodes = []
    4.         while head:
    5.             nodes.append(head.val)
    6.             head = head.next

    将linked－list问题，转化成判断一个array是否为palindrome的问题。

    复杂度分析