234.回文链表
题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
思路
1.按照原链表构建一个反向链表，如果两个链表完全相同则为回文链表
2.将原链表中的所有节点的val顺序存储在数组中后使用双指针（array[::] == array[::-1]）
3.递归
4.快慢指针
将链表的后半部分反转，然后将前半部分和后半部分进行比较。
代码
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def isPalindrome(self, head):
"""
按照原链表构建一个反向链表，如果两个链表完全相同则为回文链表
:type head: ListNode
:rtype: bool
"""
# p = head
# reversed = ListNode()
# while p is not None:
# node = ListNode(p.val)
# node.next = reversed.next
# reversed.next = node
#
# p = p.next
#
# p1 = head
# p2 = reversed.next
# while p1 and p2:
# if p1.val == p2.val:
# p1 = p1.next
# p2 = p2.next
# else:
# break
# if p1 is None and p2 is None:
# return True
# else:
# return False
reversed = self.reverseList(head)
p1 = head
p2 = reversed
while p1 and p2:
if p1.val == p2.val:
p1 = p1.next
p2 = p2.next
else:
break
if p1 is None and p2 is None:
return True
else:
return False
def isPalindrome1(self, head):
"""
将原链表中的所有节点的val顺序存储在数组中后使用双指针
:type head: ListNode
:rtype: bool
"""
p = head
vals = []
while p:
vals.append(p.val)
p = p.next
return vals[::] == vals[::-1]
def isPalindrome2(self, head):
"""
递归法
:type head: ListNode
:rtype: bool
"""
self.front_pointer = head
def recursively_check(current_node=head):
if current_node is not None:
if not recursively_check(current_node.next):
return False
if self.front_pointer.val != current_node.val:
return False
self.front_pointer = self.front_pointer.next
return True
return recursively_check()
def isPalindrome3(self, head):
"""
快慢指针
将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。
:type head: ListNode
:rtype: bool
"""
if head is None:
return True
# 找到前半部分链表的尾节点并反转后半部分链表
first_half_end = self.end_of_first_half(head)
second_half_start = self.reverseList(first_half_end.next)
# 判断是否回文
result = True
first_position = head
second_position =second_half_start
while result and second_position is not None:
if first_position.val != second_position.val:
result = False
first_position = first_position.next
second_position = second_position.next
# 还原链表并返回结果
first_half_end.next = self.reverseList((second_half_start))
return result
def end_of_first_half(self, head):
fast = head
slow = head
while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
return slow
def reverseList(self, head):
"""
递归法反转链表
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_head
def create_linked_list(self, list):
"""根据list中的所有元素构建单链表"""
l = ListNode() # 单链表头节点
r = l # 起始尾指针r指向头节点
for e in list:
node = ListNode(e)
r.next = node
r = r.next
return l.next
def print_linked_list(self, linked_list) -> None:
"""
打印单链表中的所有元素
:param linked_list: 单链表
:return: 无
"""
print("----------------------------------------")
pointer = linked_list
while pointer is not None:
print(pointer.val)
pointer = pointer.next
if __name__ == "__main__":
slt = Solution()
linked_list = slt.create_linked_list([1, 2, 2, 1])
slt.print_linked_list(linked_list)
res = slt.isPalindrome3(linked_list)
print(res)