第53期-基础结构：链表 回文链表

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

1 问题描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1:

输入: head = [1,2,2,1]
输出: true

示例 2:

输入: head = [1,2]
输出: false

示例 3:

输入: head = []
输出: true

初始代码

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class LinkList:
    def __init__(self):
        self.head=None
 
    def initList(self, data):
        while len(data)==0:return None
        self.head = ListNode(data[0])
        r=self.head
        p = self.head
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r
    def printlist(self,head):
        a=[]
        if head == None: return []
        node = head
        while node != None:
            a.append(node.val)
            node = node.next
        return a
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        #在此填写代码

if __name__ == '__main__':
    print(Solution().isPalindrome(LinkList().initList([1,2,2,1])))
    print(Solution().isPalindrome(LinkList().initList([1,2])))
    print(Solution().isPalindrome(LinkList().initList([])))

2 解题思路

• 标签：链表
• 可以将链表中的元素全部存到列表中，判断列表是否是回文列表
• 若列表是回文列表，那么链表也是回文链表

3 解题方法

# Definition for singly-linked list.
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class LinkList:
    def __init__(self):
        self.head=None
 
    def initList(self, data):
        while len(data)==0:return None
        self.head = ListNode(data[0])
        r=self.head
        p = self.head
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r
    def printlist(self,head):
        a=[]
        if head == None: return []
        node = head
        while node != None:
            a.append(node.val)
            node = node.next
        return a
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        a=[]
        while head:
            a.append(head.val)
            head=head.next
        return a==a[::-1]

if __name__ == '__main__':
    print(Solution().isPalindrome(LinkList().initList([1,2,2,1])))
    print(Solution().isPalindrome(LinkList().initList([1,2])))
    print(Solution().isPalindrome(LinkList().initList([])))

第1-30，37-40行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑（具体为创建链表以及列表、链表转换）
第31行： 创建列表a，用于存放链表中的元素数值
第32行： 当head不为None时，执行循环
第33行： 在列表a的后方加上当前head指向的节点数值
第34行： 由于head不为None，所以一定有指向下一个值，将head指针指向head.next
第35行： 当head指针指向None时，结束循环，判断列表a是否是回文列表并返回结果

代码运行结果为：

结构讲解

这里用到了基础结构：链表，简单讲解下这个链表：
链表
链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接
链表的结构：data为自定义的数据，next为下一个节点的地址。

基本元素
节点：每个节点有两个部分，左边称为值域，存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
head:head节点永远指向第一个节点
tail: tail永远指向最后一个节点
None:链表中最后一个节点的指针域为None值

4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码