（Python3）数据结构——05.单链表之链表反转的原理及实现

前言

• 有Python基础
• 建议先学下链表

https://blog.csdn.net/sf9898/article/details/104946291
           

原理

反转链表

• 没错，灵魂画手又来了

1. 如图所示，我们需要去把next的指向反转。当然，目前讨论的情况仅针对单链表。
2. 第一个节点在反转后是尾部节点（倒数第一个节点），因此它的next指向 None，下图中第二个节点反转后是倒数第二个节点，next应指向第一个节点，如图中黄线。第三个节点反转后是倒数第三个，next指向原来的第二个（现在的倒数第二个），如图。以此类推。

实现

初始化

链表的定义和初始化，这里只写了几个比较常用的功能（头部添加和遍历等），其他的可以参照以下链接 ：

https://blog.csdn.net/sf9898/article/details/104946291
           

代码

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None


class Link(object):
    def __init__(self):
        self.__head = None

    def isEmpty(self):
        return self.__head is None

    def size(self):
        count = 0
        cur = self.__head
        while cur:
            count += 1
            cur = cur.next
        return count

    def addFront(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def travel(self):
        cur = self.__head
        while cur:
            print(cur.item, end=' ')
            cur = cur.next
        print('')
           

反转

接下来实现下reverse方法

def reverse(self):
        cur = self.__head
        pre = None
        if cur:  # 当头结点不为空时才进行以下的操作，如果为空，None是没有next这个属性的，会报错
            cn = cur.next  # 头结点的下一个节点，可能为空
        while cur:
            cur.next = pre		# 改变当前节点的next指向
            pre = cur		# 更新
            cur = cn
            if cur:
                cn = cn.next  # 更新的时候需要注意是不是为空，空的话是没有next属性的
        self.__head = pre
           

完整代码

接下来做测试，以下是完整代码

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None


class Link(object):
    def __init__(self):
        self.__head = None

    def isEmpty(self):
        return self.__head is None

    def size(self):
        count = 0
        cur = self.__head
        while cur:
            count += 1
            cur = cur.next
        return count

    def addFront(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def travel(self):
        cur = self.__head
        while cur:
            print(cur.item, end=' ')
            cur = cur.next
        print('')

    def reverse(self):
        cur = self.__head
        pre = None
        if cur:  # 当头结点不为空时才进行以下的操作，如果为空，None是没有next这个属性的，会报错
            cn = cur.next  # 头结点的下一个节点，可能为空
        while cur:
            cur.next = pre
            pre = cur
            cur = cn
            if cur:
                cn = cn.next  # 更新的时候需要注意是不是为空，空的话是没有next属性的
        self.__head = pre


ll = Link()
print('size:', ll.size())
print(ll.isEmpty())

# for i in range(5):
#     ll.addFront(i)

print('size:', ll.size())
ll.travel()
ll.reverse()
ll.travel()
           

• 结果及分析：可以看到上面代码的for循环是加了注释，这里注释掉可以先验证一下空链表的情况，结果如下。

• 当然，去掉注释看下效果，看看是否实现反转。可以看到效果OK。

• 当然，也可以验证只有一个节点的情况，比如注释掉for循环，加上一句ll.addFront(1)，效果如下。更多的情况可以自己尝试。