題目
請判斷一個鏈表是否為回文鏈表形用。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進階：
你能否用 O(n) 時間復雜度和 O(1) 空間復雜度解決此題则剃？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-linked-list
著作權歸領扣網絡所有专肪。商業(yè)轉載請聯系官方授權月洛，非商業(yè)轉載請注明出處辈末。
解題思路
本題要求回文鏈表目胡，并且要求了空間復雜度O（1）。
- 首先如果沒有元素或者只有一個元素栽连，返回True。
- 使用快慢鏈表，找到中心節(jié)點秒紧。將后半部分的節(jié)點翻轉绢陌。
- 比較前面和后面列表。返回結果熔恢。
代碼
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head or not head.next:
return True
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
slow = slow.next
slow = self.reverse(slow)
while slow:
if slow.val != head.val:
return False
slow = slow.next
head = head.next
return True
def reverse(self,head):
temp = curr = None
# head
while head:
curr = head
head = head.next
curr.next = temp
temp = curr
return curr
