Skip to content

234 palindrome linked list

234. Palindrome Linked List

题目: https://leetcode.com/problems/palindrome-linked-list/

难度: Easy

蠢了一下，

思路是：“先翻转整个链表（in-place），然后和之前的链表比较”，但是这样原链表都变了，肯定错。

如果新建一个链表，然后改造成原来链表的翻转链表，还是可行的，但是空间复杂度就是O(n)了。那还不如直接把List中元素拷贝到数组中直接比较，ac代码如下：

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        vals = []
        while head:
            vals += head.val,
            head = head.next
        return vals == vals[::-1]

这道题并不能算Easy吧：

思路二： 要想实现O(1)的空间复杂度，可以找到中间的节点，把linked list拆成两个部分，后半部分linkedlist reverse，然后比较两个linked list值是否相同，看例子：

1 -> 3 -> 1 拆成 1 和 1

1 -> 3 -> 5 ->5 -> 3 -> 1 拆成 1-> 3 -> 5 和 5 -> 3 -> 1

可以使用快慢指针来找到中间的节点。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        # 找到中间节点
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        # 翻转后半部分
        prev = None
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp
        # 比较前后两部分
        while prev: # while prev and head:
            if prev.val != head.val:
                return False
            prev = prev.next
            head = head.next
        return True

给个最终状态的例子：


                       fast     tmp
           None        prev     slow
            ^           ^        ^
            |           |        |
1 --> 2 --> 3 <-- 2 <-- 1       None

但是注意最后的while prev不能换成while fast, 因为这是总节点数为奇数的情况，如果是偶数情况就不一样了，如下：

                          tmp
                          slow    
           None  prev     fast
            ^     ^        ^
            |     |        |
1 --> 2 --> 2 <-- 1       None
回到顶部