（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)，效果如下。更多的情況可以自己嘗試。