原題
設(shè)計一種方式檢查一個鏈表是否為回文鏈表。
樣例
1->2->1就是一個回文鏈表码耐。
解題思路
- 方法一：快慢指針追迟，慢指針一邊走一邊將經(jīng)過的節(jié)點放入stack，當(dāng)快指針走到終點骚腥，慢指針正好走到中點敦间，并且已經(jīng)將前半段放入stack，根據(jù)stack的特性束铭，之后依次取出跟后半段比對廓块。
- 方法二：依舊使用快慢指針，取到中點契沫，然后將后半段翻轉(zhuǎn)带猴，比較
完整代碼
# 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 head == None or head.next == None:
return True
stack = []
slow, fast = head, head
while fast != None and fast.next != None:
stack.append(slow.val)
slow = slow.next
fast = fast.next.next
if fast == None:
pass
else:
slow = slow.next
while slow != None:
cur = stack.pop()
if slow.val != cur:
return False
slow = slow.next
return True
# 方法二
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head == None or head.next == None:
return True
slow, fast = head, head
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
if fast == None:
secHalf = self.reverse(slow)
else:
secHalf = self.reverse(slow.next)
while secHalf != None:
if secHalf.val != head.val:
return False
secHalf = secHalf.next
head = head.next
return True
def reverse(self, head):
if not head:
return head
prev = None
while head != None:
temp = head.next
head.next = prev
prev = head
head = temp
return prev
