单链表反转问题


今天聊一个关于单链表反转的问题,已知一个单链表,给出头结点,现要求定义一个函数,输入头结点然后输出反转后的链表。


#链表反转前 1->2->3->4->5->6->7->8->9

#链表反转后 1<-2<-3<-4<-5<-6<-7<-8<-9

首先我一看到这个问题,想到的是利用一个数组,将单链表按顺序遍历并把每个节点的值依次存放到数组中,然后再将数组倒序输出即是反转后的链表。这种办法其实也没错,但是不够好,因为需要浪费额外的空间,且时间复杂度和空间复杂度均为 O(n)。



所以我们换一种思路来解决这个问题,能不能在遍历链表的同时就把节点的指针反向呢,这样的话只需要遍历一次链表即可完成链表反转操作。这个思路看起来很不错,但这里有一个重要的问题需要我们去解决,防止断链,因为一旦把节点的指针反向了,当前指针就不再指向下一个节点了,因此也就不能再继续往后遍历了,也就不能把这个完整的链表进行反转了,这种情况称作断链。



为了解决断链的情况,我们就需要在节点指针反向之前,就把当前节点的下一个节点先记下来,等到当前节点的指针完成反转后,遍历指针直接移动到刚刚被记住的那个节点,这样就能防止断链的情况了。



我们先定义三个指针,一个指向当前节点 curr,一个指向当前节点的前一个节点 pre,一个指向当前节点的后一个节点 pnext。当遍历到某个节点curr 时,把 pnext 指针指向 curr 的下一个节点 curr->next,即记住了当前节点的下一个节点,然后开始做指针反向操作,把 curr->next 反过来指向其前一个节点 pre,这一步已经在原地完成了当前节点的反转,接下来移动指针继续完成和上面同样的操作,即把 pre 移动到 curr,把 curr 移动到 pnext,直到所有的节点都被遍历完。



要注意的是,链表节点中的指针和自定义的三个指针是不一样的,自定义的指针是用来记录遍历节点位置的,节点中的指针只代表指向其下一个节点,这一点要注意区分,另外,在一般的高级语言中并没有指针这一说法,比如在 python 中我们称作引用,其实跟指针是一样的,都表示指向所存储对象的内存地址。



上面这种方法其实是在原地对指针进行反转,我们其实还可以用递归的方式来实现反转,使用递归来移动当前节点从而完成遍历,但是依然需要在指针反向前先记住当前节点的下一个节点。


# -*- coding: utf-8 -*- #定义链表节点,data为节点的value值,next为指向下一个节点的指针 class Node:     def __init__(self,data=None,next = None):         self.data = data
        self.next = next #定义反转函数,参数为第一个节点(头结点) def reverse(head):     #定义三个变量,分别表示当前节点、前节点(默认为None)、下一个节点(默认为None)     curr = head
    pre = None     pnext = None     #遍历链表,主要如果是空链表不会进入遍历,直接返回None     while curr:
        #先记住当前节点的下一个节点,即pre指向下一个节点的地址         pnext = curr.next
        #开始反转,把原本指向下一个节点的指针指向前一个节点         curr.next = pre
        #为了继续往后遍历,需往后移动指针         pre = curr
        curr = pnext

    return pre #递归实现反转 def recursive(curr,pre=None):     if not curr:
       return pre

    pnext = curr.next
    curr.next = pre

    return recursive(pnext,curr) if __name__ == '__main__':
    link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))    

    linkReverse = recursive(link)
    # linkReverse = reverse(link)     while linkReverse:
        print(linkReverse.data)
        linkReverse =linkReverse.next 


9 8 7 6 5 4 3 2 1  
关键词: 数据结构与算法

网友留言(0条)

发表评论