Python算法进阶 - 4(回文链表)

进阶 - 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.

之所以采用多元赋值，其重要的原因还是节省代码量，免去了中间在赋值一个新的变量。

静下心，细细品味，别有一番滋味。