反转链表( LeetCode 206 )

一、题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

二、题目解析

这道题目有很多种解法,递归解法最难以理解整个过程,今天我就带大家来探究一次!

先来看分析过程,这里看不懂没关系,一定要看最后的动画过程

  • 1、通过递归函数,一直递归到链表的最后一个结点为止,此时,该结点就是反转成功后的头结点,是最终的返回结果。
  • 2、在递归函数中,让当前节点的下一个节点的 next 指针指向当前节点。
  • 3、在递归函数中,让当前节点的 next 指针指向 null
  • 4、通过二三步的操作,已经让递归函数中的链表实现了局部反转,将结果返回给上一层递归函数
  • 5、所有递归结束后,链表反转成功。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
    public ListNode reverseList(ListNode head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下,反转之后的结果还是它自己本身
        if( head == null || head.next == null)  return head;

        // 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        ListNode cur = reverseList(head.next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候,head 为 4,那么 head.next = 5
        // 那么 head.next.next 就是 5.next ,意思就是去设置 5 的下一个节点
        // 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head;


        // head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head.next = null;

        // 我们把每次反转后的结果传递给上一层
        return cur;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下,反转之后的结果还是它自己本身
        if( head == NULL || head->next == NULL)  return head;

        // 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        ListNode *cur = reverseList(head->next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候,head 为 4,那么 head.next = 5
        // 那么 head.next.next 就是 5.next ,意思就是去设置 5 的下一个节点
        // 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head->next->next = head;


        // head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head->next = nullptr;

        // 我们把每次反转后的结果传递给上一层
        return cur;

    }
};

3、Python 代码

#  登录 AlgoMooc 官网获取更多算法图解
#  https://www.algomooc.com
#  作者:程序员吴师兄
#  代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 寻找递归终止条件
        # 1、head 指向的结点为 null 
        # 2、head 指向的结点的下一个结点为 null 
        # 在这两种情况下,反转之后的结果还是它自己本身
        if(head == None or head.next == None):
            return head

        # 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        # 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        cur = self.reverseList(head.next)

        # 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        # 第一次执行下面代码的时候,head 为 4,那么 head.next = 5
        # 那么 head.next.next 就是 5.next ,意思就是去设置 5 的下一个节点
        # 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        # 这里出现了两个 next
        # 第一个 next 是「获取」 head 的下一节点
        # 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head

        # 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        # 否则会发生无限循环
        head.next = None

        # 我们把每次反转后的结果传递给上一层
        return cur

四、动画理解(没有声音)

隐藏内容
  • 普通用户购买价格:1积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(4)

  • 惜静 永久会员 2021年10月14日 下午11:32

    Go语言
    func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
    return head
    }
    var result = reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return result
    }

  • 陈芷维 永久会员 2021年10月16日 下午8:44

    class Solution {
    // 1. 双指针
    public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    ListNode cur = head;
    while (cur != null) {
    // store the next node
    ListNode nextTmp = cur.next;
    cur.next = newHead;
    newHead = cur;
    cur = nextTmp;
    }
    return newHead;
    }
    // 2. 递归
    public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null) {
    return head;
    }
    ListNode reverse = ReverseList(head.next);
    head.next.next = head;
    head.next = null;
    return reverse;
    }
    }