当前位置:   article > 正文

反转单链表到底有多少种方法?_单链表如何翻转

单链表如何翻转

在这里插入图片描述

这是考察频率非常高的一道题目,在 LeetCode 上可以直接练习,点击《反转链表》。

这道题目,包含了一个最基本的考察点,经典数据结构单链表的实现。链表是由一个一个节点组成的,每个节点有一个数据域和一个Next指针,链表可以用一个头节点来指代。链表的下一个节点在哪里,由 Next 指针决定。

在这个基础知识的基础上,翻转一个链表就变得非常简单,Next 指针本来指向的后继节点,只要让每个节点的 Next 指针都指向前驱节点,那么,再处理好头尾边界,那么就完成了链表的翻转。
反转单链表
从逻辑上理解,题目的解法一目了然,所以,重点考核的能力是编码能力。显然需要写一个循环,将每个指针都翻转方向,但是,这很考验编码的功力和逻辑思维能力。怎么才能有条不紊的逐个翻转指针呢?

解法一:数组法

先遍历链表,将数字都取出来,放到数组里,然后反转数组,重新构造链表。因为单链表的结构过于简单,缺点过于明显,在日常工作中极其少用,而数组是不管用哪种语言的程序员都十分熟悉的接口,所以,想到使用数组代替链表进行操作。如果没有限定时间、空间复杂度,这种方法,很容易一次写正确。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        
        p = dummy = ListNode()
        for num in reversed(arr):
            p.next = ListNode(num)
            p = p.next
        
        return dummy.next
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

该算法的时间复杂度是 O ( n ) O(n) O(n),空间复杂度是 O ( n ) O(n) O(n)。在面试中,如果只能想到这种方法,是不够的。

解法二:递归法

递归,是设计算法的利器,在这个场景下,也极其简单,可能比解法一还要简单。递归法的关键是,掌握递归方法的设计思路。

设计递归方法的一种核心思路是,将问题规约成一个规模更小的问题,如果可以解决,我们就可以嵌套使用此法直到将问题规约到最平凡的问题。以本题为例,给定一个链表,如何将其规约成更小的问题呢?例如,我们可以去掉一个节点后,将少了一个节点的链表进行反转。

假设我们已经拥有了一个方法 f f f,可以将少了一个节点的链表反转,那么,我们如何将整个链表反转呢?十分简单,先将去掉头节点的链表反转,然后将头节点连接到反转结果的末尾,就完成了整个链表的反转。那么,我们就可以递归调用这个方法 f f f。直到链表只剩下一个节点,或者没有节点。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: 
            return head
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newHead
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

上面的代码里,首先是递归的最平凡用例,空链表,或者链表只有一个节点,可以直接返回。然后,我们将除头节点以外的部分反转,然后我们将头节点连接到新链表的末尾,就大功告成。

递归算法的设计,精巧简单,实现便利,一般都能无往不利。难点一般在于边界条件,以及复杂度分析。比如,上面写的这个算法,边界条件为什么是两个——空链表和单节点链表?因为,我们规约问题的时候,每次去掉一个节点,总会使得链表最终剩余 0 个节点,那么边界条件我们是不是只考虑 0 个节点就行呢?请自行思考。

递归算法的复杂度分析,比较困难,一般需要有算法学习基础才能掌握基本分析方法。但是也有不少取巧的方法,比如在这个例子里,我们可以在脑海里很形象地想象递归栈展开后的情形,每次摘掉一个节点,等着后面的反转,一旦到达末尾节点,所有递归栈逐级返回,显然,时间复杂度是 O ( n ) O(n) O(n)。空间复杂度是栈的深度,也是 O ( n ) O(n) O(n)

解法三:迭代法

使用迭代法反转链表
一般解决单链表问题的一个窍门,就是画图示意。上图,是一个已经反转了两个节点的链表的反转过程。如图,我们先切断3、4的连接,然后将 3 指向 2。然后将 Tail 和 Head 指针都往前挪。

对于反转单链表这道题目,记住这个算法窍门就是,“把头变成尾巴”,就能完成反转,一开始尾巴是空的,然后把头节点一个一个接到尾巴上,最后,整条链表变成了尾巴。有了这个思路,无论是画图推导,还是代码编写,都会迎刃而解。这个方法也很容易记忆。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        tail = None
        while head:
            temp = head.next
            head.next = tail
            tail = head
            head = temp
        return tail
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

如上代码,迭代的时候,我们先用一个 temp 变量记住头节点的下一个位置,然后,就可以开始交换,首先将头节点接到尾巴上,然后尾巴往前移,原来的头节点变成了新的尾巴的开始,然后头节点指向一开始暂存 temp 的位置,开始下一轮。Python 支持多重赋值,利用语法糖,这个代码还可以写得更简单。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        tail = None
        while head:
            head.next, tail, head = tail, head, head.next
        return tail
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

这个写法看着很优雅,但是很不容易写对,也不容易读懂,不是很推荐。

这个算法的复杂度显然是 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1)。这个方法是比较高效,一般也是面试中能够出彩的方案。不过,不通过自己推理,多次编写来练习,一般很难写到这么精简。

— END —

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/1016858
推荐阅读
相关标签
  

闽ICP备14008679号