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



回到顶部