01-18 10:08 阅读 99

Python判断回文链表的方法

这篇文章主要介绍了Python判断回文链表,本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下

什么是回文数？

回文数简单的说就是正着倒着读都是一样的，比如：12321,1221,1111等等，正着读也是12321，倒着读也是12321。

首先，接收用户输入数字列表转换成链表

比如用户输入：1 2 3 2 1，转换为链表后，如下图

首先接收用户输入数字列表，每个数字用空格分隔，使用split截断字符串，使用map，把每个元素映射成int类型，然后再转成list，使用循环取出每项元素添加到链表中。

1	`lt` `=` `list(map(int, s.split(' ')))`

代码如下：

# 链表类

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

# 字符串转换为链表

def list_node(s):

    lt = list(map(int, s.split(' ')))

    l = ListNode(0)  # 创建头节点为0的链表

    p = l

    for i in range(len(lt)):

        p.next = ListNode(lt[i])

        p = p.next

    return l.next

判断是否是回文

找中间位置处使用快慢指针法，慢指针一次跳一格，快指针一次跳2格，所以快指针是慢指针的2倍，当快指针为None时，说明链表结束了，也就是代码中的fast.next.next=None时，链表结束，此时慢指针刚好指着链表的中间位置，所以就得到3是中间位置，从3的下一个位置。再将中间位置的下一个节点开始的链表，进行倒叙，也就是21，倒叙后为12。

再与中间位置前面一段链表进行比较是否相等，如果p==None时说明链表为None，直接返回True，p==None，q也一定为None（具体看后面的倒叙方法）

1

2

3

4

while p is not None and q is not None:

        if p.val is not q.val:

            return False

        q, p = q.next, p.next

完整代码：

# 是否是回文

def palindrome(l):

    if l is None:

        return True

    slow = fast = l

    # 查找中间节点，一快一慢指针，快的是慢的2倍，当快指针为None时，说明已经找到中间节点了

    while fast.next is not None and fast.next.next is not None:

        slow = slow.next  # 慢指针每次向后移一个位置

        fast = fast.next.next  # 快指针每次向后移2个位置

    h = slow.next

    q = reverse(h)  # 逆至无头节点链表

    slow.next = None

    p = l

    while p is not None and q is not None:

        if p.val is not q.val:

            return False

        q, p = q.next, p.next

    if q is None:

        return True

    else:

        return False

倒叙链表（头插法）：声明一个头节点，然后遍历每个节点，再头插到链表里面，总共是4步；

第1步：保存当前头节点所只向的节点

第2步：使当前节点指向头节点所指向的节点

第3步：使头节点只向当前节点

第4步：使指针（p）指向下一个节点，指向下一次循环

头插法图解：

完整代码：

# 逆置不带头结点的单链表

def reverse(head):

    h = ListNode(0)

    p = head

    while p is not None:

        x = p.next  # 保存着当前节点指向的下一个节点

        p.next = h.next  # 当前项的指向节点指向头节点指向的节点

        h.next = p  # 头节点再指向当前节点

        p = x  # 使节点指向下一个节点

    return h.next

完整代码

# 回文链表，输入1->2输出false,输入1->

# 链表类

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

# 字符串转换为链表

def list_node(s):

    lt = list(map(int, s.split(' ')))

    l = ListNode(0)  # 创建头节点为0的链表

    p = l

    for i in range(len(lt)):

        p.next = ListNode(lt[i])

        p = p.next

    return l.next

# 逆置不带头结点的单链表

def reverse(head):

    h = ListNode(0)

    p = head

    while p is not None:

        x = p.next  # 保存着当前节点指向的下一个节点

        p.next = h.next  # 当前项的指向节点指向头节点指向的节点

        h.next = p  # 头节点再指向当前节点

        p = x  # 使节点指向下一个节点

    return h.next

# 是否是回文

def palindrome(l):

    if l is None:

        return True

    slow = fast = l

    # 查找中间节点，一快一慢指针，快的是慢的2倍，当快指针为None时，说明已经找到中间节点了

    while fast.next is not None and fast.next.next is not None:

        slow = slow.next  # 慢指针每次向后移一个位置

        fast = fast.next.next  # 快指针每次向后移2个位置

    h = slow.next

    q = reverse(h)  # 逆至无头节点链表

    slow.next = None

    p = l

    while p is not None and q is not None:

        if p.val is not q.val:

            return False

        q, p = q.next, p.next

    if q is None:

        return True

    else:

        return False

if __name__ == '__main__':

    print("回文链表")

    l = list_node(input())

    print(palindrome(l))

运行结果图：

到此这篇关于Python判断回文链表的文章就介绍到这了

原文链接：https://blog.csdn.net/baidu_39105563/article/details/122202246