python实现单链表的翻转

左手的ㄟ右手 2023-03-12 13:29 5阅读 0赞

关于线性表的实现可以参考：[python实现线性表][python]  
python实现单链表的翻转实现思路：  
从头指针开始遍历，先获取头指针的下一个结点保留，然后调整头指针的指向，然后再把之前保留的节点赋给头结点，继续遍历

class LinkNode(object):
        def __init__(self, elem):
            self.elem = elem
            self.next = next
    
    class Linklist(object):
        def __init__(self):#单链表头指针为空
            self.head=None
        #翻转链表
        def reverseList(self):
            if self.head == None or self.head.next == None:  # 若链表为空或者仅一个数就直接返回
                return self.head
            pre = None
    
            while (self.head != None):
                next = self.head.next #为了防止断链
                self.head.next = pre#链表转向
                pre = self.head #pre就是一个临时值，用于链表指针的转向的同时防止断链
                self.head = next#继续往前走
            return pre
    
    
        #头插法建表
        def headcreatelink(self,elem):
            nod=LinkNode(elem)
            nod.next=self.head
            self.head=nod
        #链表遍历
        def travelList(self):
            res=[]
            nod=self.head
            while nod!=None:
                res.append(nod.elem)
                nod=nod.next
            return res
    
    
    if __name__ == '__main__':
        l1=Linklist()
        rr=LinkNode(None)
        for i in range(5):
            l1.headcreatelink(i)
        t=l1.travelList()
        print(t)
        #得到翻转后的头指针
        s=l1.reverseList()
        print(type(s))
        while s!=None:
            print(s.elem)
            s=s.next

运行结果为：

[4, 3, 2, 1, 0]
    <class '__main__.LinkNode'>
    0
    1
    2
    3
    4

[python]: https://blog.csdn.net/liulanba/article/details/113720473