链表的实现、输出和反向 python

　　链表节点包含两个元素：节点的值和指向的下一个节点，因此可以定义链表的类为：

class linknode:

    def __init__(self,value=None,next=None):

        self.value=value

        self.next=next

　　给定一个列表l，用此列表生成一个链表时，只需按顺序遍历列表，使用遍历到的值生成链表节点，并在前后两个节点之间建立联系，最后返回头节点。

def createlink(l):

    head=linknode(l[0])

    nn=head

    for i in l[1:]:

        nn.next=linknode(i)

        nn=nn.next

    return head

　　输出一个链表，按顺序访问列表节点即可。

def printlist(head):

    if head==None: return

    node=head

    while node!=None:

        print(node.value)

        node=node.next

　　链表的反向是指对链表的方向进行反转。如给定链表：1->2->3->4->5，

反向后的链表为：5->4->3->2->1

反向的关键在于，在反向的过程中，不能丢掉了原来链表节点之间的联系，如对前两个节点反向时，执行2.next=1后，则对于前两个节点，方向为2->1

但对于整个链表来说，由于2.next已经被更新，链表成为

就无法继续访问后续节点。所以，在反向的过程中，要记录的节点有三个：前一个节点pre，当前节点cur，下一个节点next，这样，在执行cur.next=pre后，还可以继续对next进行操作，代码如下。

def reverselink(head):

    if head==None: return

    if head.next==None: return head

    reversehead=None

    pre,cur,next=None,head,head.next

    while next!=None:

        cur.next=pre

        pre=cur

        cur=next

        next=next.next

    else:reversehead=cur

    return reversehead

巴特西

链表的实现、输出和反向 python

最新文章

热门文章