LeetCode 234. 回文連結清單

題目

請判斷一個連結清單是否為回文連結清單。

示例 1:

輸入: 1->2
輸出: false
示例 2:

輸入: 1->2->2->1
輸出: true           

進階：

你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題？

解題思路

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # tempList = []
        # while head != None:
        #     tempList.append(head.val)
        #     head = head.next
        # if tempList[:] == tempList[::-1]:
        #     return True
        # return False
        #快慢指針處理，快指針是慢指針兩倍，快指針到盡頭，慢指針剛好到中間，然後把慢指針之前的反轉，然後兩邊進行對比，要注意奇數偶數的差異
        left = right = head
        pre = None
        ret = True
        while right and right.next:
            right = right.next.next
            #反轉連結慢指針所到之處的連結
            tempCur = left.next
            left.next = pre
            pre = left
            left = tempCur
        RHead = left #反轉連結與正傳的頭的交接點，用于恢複原狀的時候搭接
        #偶數
        if right == None:
            right = left
            left = pre
        #奇數
        elif right.next == None:
            right = left.next
            left = pre
        while right and left:
            if right.val == left.val:
                right = right.next
                left = left.next
            else:
                ret = False
                break
        #恢複反轉連結的原狀
        left = pre
        pre = RHead
        while left:
            tempCur = left.next
            left.next = pre
            pre = left
            left = tempCur
        return ret

if __name__ == '__main__':
    #連結清單樣例
    #L1 1->2->3->4->5
    l1 = ListNode(1,ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    #L2 1->3->4
    l2 = ListNode(1, ListNode(3, ListNode(4)))
    ret = Solution().isPalindrome(l1)
    print(ret)
    # print(ret.val)
    # print(ret.next.val)
    # print(ret.next.next.val)
    # print(ret.next.next.next.val)
    # print(ret.next.next.next.next.val)