1.回文链表
请判断一个链表是否为回文链表。
示例 1: 输入: 1->2 输出: false
示例 2: 输入: 1->2->2->1 输出: true
算法分析：
首先我们得明白什么是回文数，回文数就是无论是从左往右，从右往左读都是一个数的数字，如121、1221，,12321等等，那么放到链表里它的概念也是一样的，区别就是每个数字还带了一个指向下一个数字的指针而已。
下面我就说说我对这道题的解法：
回文数都是对称的，我们可以先遍历整个链表，得到链表的长度，这样我们就可以知道这个链表的一半在哪，最最重要的时，在遍历的同时，我们需要将所有的结点全部压栈，作用等会就懂了。
length = 0 # 初始化链表长度为0
stack = [] # 定义一个空栈
originHead = head # 保存原本链表的头结点
while head:
length += 1 # 长度+1
stack.append(head) # 结点压栈
head = head.next # 让结点后移
经过一次遍历，我们得到了链表的长度并且将链表结点全部压栈，这时候我们就可以得到链表的一半为
middle = length // 2 # 取整数部分
不管链表长度是奇数还是偶数，我们只需要对它长度的一半向下取整即可，因为如果它是回文链表的话，第middle+1的位置是不影响的，就比如636长度是3，middle是1，第2的位置也就是3，是不影响它成为回文数的。
这时候我们可以开始判断它是不是回文链表了，怎么做呢？
我们都知道，栈是先进后出的，我们将链表压栈再出栈的时候，结点位置是与链表里的位置相反的，我们根据栈的这个性质，可以进行如下操作：
while middle >= 0:
node = stack.pop() # 结点出栈
# 若与头结点所在的那一半的元素不等于与它对称的元素
if node.val != originHead.val:
return False
originHead = originHead.next # 头结点所在一半的结点后移
middle -= 1
上面我们是通过一个middle次的循环，一一对比头尾对称的两个元素，如果有一对不相等，返回False，循环结束后，返回True。
全部代码：
# 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:
if not head:
return False
length = 0
stack = []
originHead = head
while head:
length += 1
stack.append(head)
head = head.next
middle = length // 2
while middle >= 0:
node = stack.pop()
if node.val != originHead.val:
return False
originHead = originHead.next
middle -= 1
return True
利用了栈先进后出的特性，实现了这个算法。
2.环形链表
给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true。否则，返回 false 。
算法分析：
这是一个很典型的快慢指针的应用场景了，什么是快慢指针呢，举个例子，在操场上跑步的时候，如果一个人跑的很慢，另外一个较快，因为跑道是环形的，所以这两人只要一直在跑步，那么肯定就会相遇，我们根据这个生活常识就可以解答这道题。
直接给出算法：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# 首先判断链表是否为空或没有下一个结点
if not head or not head.next:
return False
slow = head # 慢指针
fast = head # 快指针
while fast and fast.next: # 当快指针不为None且有下一个结点
slow = slow.next # 慢指针后移
fast = fast.next.next # 快指针每次比慢指针多移动一个结点
if fast == slow: # 若两指针相遇
return True
return False
算法很简单，就是模拟两人跑步，一个快一个慢，判断他俩是否会交会就可以解答这道题了。
如果你对上面的算法有更好的想法，可以在评论区说出你的看法哦~
PS：以上题目均来自LeetCode
线性表 Python版权声明：如无特殊说明，文章均为本站原创，转载请注明出处
本文链接：https://www.yangyingqi.com/51.html
