美文网首页程序员Python
001单链表逆序就地逆序法

001单链表逆序就地逆序法

作者: DKider | 来源:发表于2019-02-07 15:08 被阅读38次

    题目
    给定一个带头节点的单链表:
    head->1->2->3->4->5->6->7->8
    使其成为:
    head->8->7->6->5->4->3->2->1

    就地逆序法(这是方法一,后续会有其他方法)

    python语言中并没有指针和数组,因此用引用来实现
    先定义一个节点对象——有数据和后续节点地址两部分组成

    class LNode:
    def __init__(self, x):
        self.data = x
        self.next = None
    
    def Reverse(head):
    ''' 有头节点
    :param head:
    :return:
    '''
    # 判断链表是否为空
    if head is None or head.next is None:
        return
    pre = None
    cur = None
    next = None
    # 处理链表头
    cur = head.next
    next = cur.next
    cur.next = None
    pre = cur
    cur = next
    # 转变当前节点指向
    while cur.next != None:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    # 处理最后一个节点与倒数第二个节点
    cur.next = pre
    # 添加头节点
    head.next = cur
    
    if __ name __ == '__main __':
    i = 1
    head = LNode(None)
    # head.data=None
    # head.next=None
    cur = head
    tmp = None  # 用作添加新节点
    # 构造单链表
    while i <= 8:
        tmp = LNode(i)
        # tmp.data=i
        # tmp.next=None
        cur.next = tmp
        cur = tmp
        i += 1
    print("BeforeReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next
    print("\nAfterReverse:")
    Reverse(head)
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next
    

    输出如下:(我用的pycharm)


    image.png

    写在最后:
    我对Markdown语法还不太熟悉,不太明白怎么把代码正确的显示出来。例如上面的if __ name __ == "__ main __" 我不能使它成为代码的一部分,这让我很头疼。请大家教教我谢谢。
    本文代码在我的Github上有“https://github.com/Gesujian/python-”如发现错误请指正,谢谢^ _^

    相关文章

      网友评论

        本文标题:001单链表逆序就地逆序法

        本文链接:https://www.haomeiwen.com/subject/swzwsqtx.html