专栏首页编程拯救世界图解精选 TOP 面试题 005.1 | 反转链表之递归求解

图解精选 TOP 面试题 005.1 | 反转链表之递归求解

该系列题目取自 LeetCode 精选 TOP 面试题列表:https://leetcode-cn.com/problemset/top/

题目描述

LeetCode 206. 反转链表:https://leetcode-cn.com/problems/reverse-linked-list/

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

解题思路

在上一篇《图解精选 TOP 面试题 005 | 反转链表之迭代求解》中,我们介绍了该题的迭代求解法,本篇再说说如何进行递归求解。

首先,在写代码前,我们需要先进行「递归设计」,即明确三点:

  1. 递归函数的作用
  2. 何时结束递归
  3. 何时进行递归调用

函数作用

递归函数的作用为:改变当前节点下一个节点的 next 指针,使其指向当前节点

听起来有点拗口,用代码表示就是这样的:

# 当前节点的下一个节点
next_node = head.next
# 改变下一个节点的指针
next_node.next = head

我们用这样的方式就完成了某两个节点之间指向的反转

除此之外,为了防止链表循环,我们还要切断当前节点的 next 指向,即设 head.next 为空。

何时结束

当节点为空或节点的 next 节点为空时,返回当前节点。

这样的结束条件我们可以理解为:空节点或只有一个节点时,它的反转就是其本身

何时调用

在迭代法中,我们为了反转与遍历,不断地保存上一个节点与下一个节点,整个过程显得小心翼翼。而在递归中,我们先根据链表原有的顺序利用递归将节点依次入栈,之后再层层弹出,从而反转节点之间的指向。

因此,在节点不为空且节点的下一个节点不为空时,我们进行递归调用,以此不断地将当前节点的下一个节点压入栈区,直至链表尾部。

反转过程演示

以题目中的 1->2->3->4->5->NULL 为例,整个反转过程如下:

反转过程

具体实现

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        # 不断往后获取节点
        cur = self.reverseList(head.next)
        # 反转节点指向
        next_node = head.next
        next_node.next = head
        # 切断当前节点的 next 指向
        head.next = None

        return cur

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    cur := reverseList(head.Next)
    nextNode := head.Next
    nextNode.Next = head
    head.Next = nil

    return cur
}

复杂度

  • 时间复杂度 ,n 为链表长度。
  • 空间复杂度 ,由于使用递归调用,需要考虑调用栈的情况。

本文分享自微信公众号 - 编程拯救世界(CodeWarrior_),作者:江子抑

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 精选 TOP 面试题 001 | LeetCode 237. 删除链表中的节点

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

    江不知
  • 图解精选 TOP 面试题 005 | 反转链表之迭代求解

    链表反转在面试中非常常见,我也在面试中遇到过这道题。在本篇文章中我们先说说如何用迭代法求解该题。

    江不知
  • 图解精选 TOP 面试题 004 | LeetCode 108. 将有序数组转换为二叉搜索树

    本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

    江不知
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • 单链表逆序

    第二个题目是很经典的“单链表逆序”问题。很多公司的面试题库中都有这道题,有的公司明确题目要求不能使用额外的节点存储空间,有的没有明确说明,但...

    后端技术漫谈
  • 【链表问题】打卡9:将单链表的每K个节点之间逆序

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • 【链表问题】环形单链表约瑟夫问题

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢

    帅地
  • Python实现单链表

    class Node: '''节点结构''' def __init__(self, data, nextNode=None): #设置当前节点的值和指向下...

    Python小屋屋主
  • 每天一算:Reverse Linked List

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动