进阶 - 4(回文链表)"/>
Python算法进阶 - 4(回文链表)
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
第一种算法采用
def isPalindrome(self, head: ListNode) -> bool:vals = []current_node = headwhile current_node is not None:vals.append(current_node.val)current_node = current_node.nextreturn vals == vals[::-1]
这是官方的给的题解
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def isPalindrome(self, head: ListNode) -> bool:res = []while(head):res.append(head.val)head = head.nextif len(res) <= 1:return Trueelse:n = len(res) for i in range(n // 2):if res[i] != res[n-1-i]:return Falsereturn True
官方给出的代码比较简洁。补充一下切片的知识
>>>a[:] #从左往右
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>a[::]#从左往右
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>a[::-1]#从右往左
>>> [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
熟练操作切片,看起来是可以节省工作量 但是链表题用数组的方式去做,怎么说也有点欠了一点感觉
第二种算法:
用双指针和反转链表的方法解决问题
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""# 边界条件不用忘记了if not (head and head.next):return Truep = ListNode(-1)p.next,low,fast = head,p,p# 快慢指针不断迭代,找到中间节点while fast and fast.next:low,fast = low.next, fast.next.nextcur,pre = low.next,Nonelow.next = None#将链表一分为二之后,反转链表后半部分while cur:cur.next,pre,cur = pre,cur,cur.nexta,b = p.next,pre# 将链表前半部分和 反转的后半部分对比while b:if a.val!=b.val:return Falsea,b = a.next,b.nextreturn True
首先是实现这个代码的逻辑:
是通过双指针 快慢指针的方式 慢指针刚好停留在链表的中间节点 然后将链表分成两部分 后半部分进行反转 然后与前半部分进行对比
代码中运用最多的是多元赋值,补充一点多元赋值的小知识
顾名思义:将多个变量同时进行赋值 采用这种赋值之后等号两边的对象都是元组。还有一点就是在python中等号的作用相当于指针,指向那个对象的内存。a = 10 a是一个新创建的内存 10也有一个内存 ,内在其实是a->10.
之所以采用多元赋值,其重要的原因还是节省代码量,免去了中间在赋值一个新的变量。
静下心,细细品味,别有一番滋味。
更多推荐
Python算法进阶 - 4(回文链表)
发布评论