[数据结构与算法]python链表逆转(代码附效果)

本博文源于《程序设计竞赛入门》，主要针对链表逆转进行研究，文章共分为：①题目再现 ②源码测试演示 ③核心代码分析

$\text{§}1.题目再现$

输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表进行就地转置(不增加新结点)，并输出逆置后的单链表结点数据
Input:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据,每组测试输入多个整数，以-1作为该组测试的结束(-1不处理)
Output
对于每组测试，输出逆置后的单链表数据(数据之间留一个空格）

Input:
1
1 2 3 4 5 -1

Output:
5 4 3 2 1 

$\text{§}2.源码测试演示$

$\text{§}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链接到头结点之后

$\text{§}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)