python連結清單逆轉(代碼附效果)

本博文源于《程式設計競賽入門》，主要針對連結清單逆轉進行研究，文章共分為：①題目再現 ②源碼測試示範 ③核心代碼分析

§   1. 題 目 再 現 \text{\sect}\ \ 1.題目再現 §  1.題目再現

輸入多個整數，以-1作為結束标志，順序建立一個帶頭結點的單連結清單，之後對該單連結清單進行就地轉置(不增加新結點)，并輸出逆置後的單連結清單結點資料

Input:

首先輸入一個正整數T，表示測試資料的組數，然後是T組測試資料,每組測試輸入多個整數，以-1作為該組測試的結束(-1不處理)

Output

對于每組測試，輸出逆置後的單連結清單資料(資料之間留一個空格）

Input:
1
1 2 3 4 5 -1

Output:
5 4 3 2 1 
           

§   2. 源 碼 測 試 演 示 \text{\sect}\ \ 2.源碼測試示範 §  2.源碼測試示範

§   3. 核 心 代 碼 分 析 \text{\sect}\ \ 3.核心代碼分析 §  3.核心代碼分析

将每條的注釋寫在代碼後,主要原理就是，擷取拿變量接頭結點位址，然後不斷跳，

def reverse(head):
    p = head.next # head為頭結點
    head.next = None # 頭結點指針域職=
    while p != None: # 當連結清單還沒有掃描結束
        q = p       # q 指向結點p（原連結清單的第一個資料結點）
        p = p.next  # p 指向 下一個結點
        q.next = head.next # 結點q連接配接到第一個資料結點(第一次為None)之前
        head.next = q     # 結點q連結到頭結點之後
           

§   4. 附 上 源 碼 \text{\sect}\ \ 4.附上源碼 §  4.附上源碼

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
def createByTail(a):
    head = Node(-1)
    tail = head
    for i in range(len(a)):
        p = Node(a[i])
        tail.next = p
        tail = p

    return head

def output(head):
    p = head.next
    while p!=None:
        if p!= head.next:
            print(' ',end='')
        print(p.data,end='')
        p = p.next
    print()

def reverse(head):
    p = head.next
    head.next = None
    while p != None:
        q = p
        p = p.next
        q.next = head.next
        head.next = q

if __name__ == '__main__':
    T = int(input())
    for t in range(T):
        a = list(map(int,input().split()))
        a = a[:len(a)-1]
        h = createByTail(a)
        reverse(h)
        output(h)