回文
回文结构就是倒着念和正着念没啥区别，比如12321，123321这样的。
如果判断一个链表是否符合回文结构
因为链表不能直接使用索引定位内存位置，所以必须要从头结点开始遍历。
我的一个办法是使用快慢指针找到中间位置，然后判断前后的结点是否相同。
代码
py链表
from typing import Optional
class Node:
def __init__(self, data: int, next_node=None):
self.data = data
self.next = next_node
class MySinglyLinkedList:
# 构造的时候声明头结点
def __init__(self):
# 头结点不计入链表长度
self._head = Node(0)
self._len = 0
def getHead(self):
return self._head
# 根据value查找node
def findByValue(self, value: int) -> Optional[Node]:
p = self._head.next
while p and p.data != value:
p = p.next
return p
# 根据索引查找node
def findByIndex(self, index: int) -> Optional[Node]:
p = self._head
position = 0
while p and position != index:
p = p.next
position += 1
return p
# 将值插入链表头部
def insertValueToFirst(self, value: int):
newNode = Node(value)
self.insertNodeToFirst(newNode)
# 将node插入链表头部
def insertNodeToFirst(self, node : Node):
if node:
node.next = self._head.next
self._head.next = node
self._len += 1
# 将值插入链表尾部
def insertValueToLast(self, value: int):
newNode = Node(value)
self.insertNodeToLast(newNode)
# 将node插入链表尾部
def insertNodeToLast(self, node: Node):
p = self._head
while p.next:
p = p.next
node.next = p.next
p.next = node
self._len += 1
# 在某个结点前插入值
def insertValueBeforeNode(self, value: int, node: Node):
newNode = Node(value)
self.insertNodeBeforeNode(newNode, node)
# 在某个结点前插入node
def insertNodeBeforeNode(self, new_node: Node, node: Node):
p = self._head
while p.next and p.next != node:
p = p.next
new_node.next = p.next
p.next = new_node
self._len += 1
# 在某个结点后插入value
def insertValueAfterValue(self, value: int, node: Node):
newNode = Node(value)
self.insertNodeAfterNode(newNode, node)
# 在某个结点后插入node
def insertNodeAfterNode(self, new_node: Node, node: Node):
if not node or not new_node:
return
new_node.next = node.next
node.next = new_node
self._len += 1
# 根据值删除结点
def deleteByValue(self, value: int):
head = self._head
prev = head
current = self._head.next
while current:
if current.data != value:
prev.next = current
prev = prev.next
current = current.next
self._head = head
self._len -= 1
# 根据node删除结点
def deleteByNode(self, node: Node):
if node.next:
node.data = node.next.data
node.next = node.next.next
return
p = self._head
while p.next and p.next != node:
p = p.next
if not p.next:
return
p.next = p.next.next
self._len -= 1
def __repr__(self) -> str:
nums = []
current = self._head
while current:
nums.append(current.data)
current = current.next
return "->".join(str(num) for num in nums)
# 重写__iter__方法，方便for关键字调用打印值
def __iter__(self):
node = self._head
while node:
yield node.data
node = node.next
# 打印自身结点
def printAll(self):
p = self._head.next
while p:
print(f"->{p.data}", end="")
p = p.next
print("\n", flush=True)
# 打印传入结点
def printNodes(self, node: Node):
if node:
while node:
print(f"->{node.data}", end="")
node = node.next
print("\n", flush=True)
# 单链表反转，需要改变原来的链表顺序
def reverse(self):
p = self._head.next
reverseList = None
while p:
tmp = p.next
p.next = reverseList
reverseList = p
p = tmp
self._head.next = reverseList
return reverseList
# 单链表反转，不改变原来的链表顺序
def reverse2(self):
p = self._head.next
reverseList = None
while p:
tmp = Node(0)
tmp.data = p.data
tmp.next = reverseList
reverseList = tmp
p = p.next
return reverseList
if __name__ == "__main__":
l = MySinglyLinkedList()
l.insertValueToFirst(1)
l.insertValueToFirst(2)
l.insertValueToFirst(3)
l.insertValueToFirst(3)
l.insertValueToFirst(4)
l.insertValueToFirst(5)
# l.print_all()
# print(l.findByIndex(2).data)
# print(l.findByValue(3).data)
# 在尾部插入100110120
# l.insertValueToLast(100110120)
# 在结点3前插入100
# l.insertValueBeforeNode(100, l.findByValue(3))
# 在结点100前插入250
# l.insertValueBeforeNode(250, l.findByValue(100))
# 在结点5后面插入123
# l.insertValueAfterValue(123, l.findByValue(5))
# 在结点1后面插入234
# l.insertValueAfterValue(234, l.findByValue(1))
# 删除value为指定值的结点
# l.deleteByValue(3)
# 删除node
# l.deleteByNode(l.findByValue(3))
l.printAll()
# 单链表反转
# l.printNodes(l.reverse2(l.getHead()))
# l.printAll()
判断链表是否回文
# 是否是回文链表
def palindrome(head: Node) -> bool:
# 使用快慢指针，当快指针走完的时候，慢指针在中间位置
# 记录慢指针每一步的结点数据，形成前半段的反序链表
# 从继续将慢指针走完，每一步都与前半段的反序链表做对比
slow, fast = head.next, head.next
fast = fast.next if fast else None
reverseList = Node(0)
while fast and fast.next:
tmp = Node(0)
tmp.data = slow.data
tmp.next = reverseList
reverseList = tmp
slow, fast = slow.next, fast.next.next
# 针对奇数长度链表特殊处理
if not fast:
slow = slow.next
# 针对偶数长度链表特殊处理
elif not fast.next:
slow = slow.next
tmp = Node(0)
tmp.data = slow.data
tmp.next = reverseList
reverseList = tmp
while slow:
if slow.data != reverseList.data:
return False
slow = slow.next
reverseList = reverseList.next
return True
if __name__ == "__main__":
list = MySinglyLinkedList()
list.insertValueToLast(1)
list.insertValueToLast(2)
list.insertValueToLast(3)
list.insertValueToLast(4)
list.insertValueToLast(5)
list.insertValueToLast(6)
list.insertValueToLast(7)
list.printAll()
# print('中间结点： ', findMiddleNode(list.getHead()).data)
print('list是否回文字符串： ', palindrome(list.getHead()))
list2 = MySinglyLinkedList()
list2.insertValueToLast(1)
list2.insertValueToLast(2)
list2.insertValueToLast(3)
list2.insertValueToLast(2)
list2.insertValueToLast(1)
print('list2是否回文字符串： ', palindrome(list2.getHead()))
list3 = MySinglyLinkedList()
list3.insertValueToLast(1)
list3.insertValueToLast(2)
list3.insertValueToLast(3)
list3.insertValueToLast(3)
list3.insertValueToLast(2)
list3.insertValueToLast(1)
print('list3是否回文字符串： ', palindrome(list3.getHead()))
