标签搜索

目 录CONTENT

文章目录

递归反转链表的一部分.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 3 阅读 / 2,543 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

递归反转链表的一部分

反转单链表的迭代实现不是⼀个困难的事情, 但是递归实现就有点难度了,如果再加⼀点难度, 让你仅仅反转单链表中的⼀部分, 你是否能够递归实现呢?

本⽂就来由浅⼊深, 逐步地解决这个问题。 如果你还不会递归地反转单链表也没关系, 本⽂会从递归反转整个单链表开始拓展, 只要你明⽩单链表的结构, 相信你能够有所收获

// 单链表节点的结构
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

什么叫反转单链表的⼀部分呢, 就是给你⼀个索引区间, 让你把单链表中这部分元素反转, 其他部分不变
在这里插入图片描述

迭代的思路⼤概是: 先⽤⼀个 for 循环找到第 m 个位置, 然后再⽤⼀个 for 循环将 m 和 n 之间的元素反转

但是我们的递归解法不⽤⼀个 for 循环, 纯递归实现反转

⼀、 递归反转整个链表

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    
    ListNode last = reverse(head.next);
    head.next.next = head;//相当于把head的next个节点的next指针指向自己
    //此时head节点和head的next节点之间相当于双向链表

	//断开head指向next个节点的指针,因为代码走到这里说明
	//head的下一个next节点的next指针已经指向head节点了
	//完成反转功能
    head.next = null;
    
    return last;
}

我们下⾯来详细解释⼀下这段代码

对于递归算法, 最重要的就是明确递归函数的定义。 具体来说, ==我们的reverse 函数定义是这样的:输⼊⼀个节点 head , 将「以 head 为起点」 的链表反转, 并返回反转之后的头结点==

明⽩了函数的定义, 在来看这个问题。 ⽐如说我们想反转这个链表:

在这里插入图片描述

那么输⼊ reverse(head) 后, 会在这⾥进⾏递归:

ListNode last = reverse(head.next);

不要跳进递归(你的脑袋能压⼏个栈呀? ) , ⽽是要根据刚才的函数定义,来弄清楚这段代码会产⽣什么结果:

在这里插入图片描述

这个 reverse(head.next) 执⾏完成后, 整个链表就成了这样:
在这里插入图片描述

并且根据函数定义, reverse 函数会返回反转之后的头结点, 我们⽤变量last 接收了

现在再来看下⾯的代码:

head.next.next = head;

在这里插入图片描述

接下来:

head.next = null;
return last;

在这里插入图片描述

神不神奇, 这样整个链表就反转过来了! 递归代码就是这么简洁优雅, 不过其中有两个地⽅需要注意:

1、 递归函数要有 base case, 也就是这句:

if (head.next == null) return head;
意思是如果链表只有⼀个节点的时候反转也是它⾃⼰, 直接返回即可。

2、 当链表递归反转之后, 新的头结点是 last , ⽽之前的 head 变成了最后⼀个节点, 别忘了链表的末尾要指向 null:

head.next = null;

理解了这两点后, 我们就可以进⼀步深⼊了, 接下来的问题其实都是在这个
算法上的扩展。

⼆、 反转链表前 N 个节点

这次我们实现⼀个这样的函数:

// 将链表的前 n 个节点反转(n <= 链表⻓度)
ListNode reverseN(ListNode head, int n)

⽐如说对于下图链表, 执⾏ reverseN(head, 3)
在这里插入图片描述
解决思路和反转整个链表差不多, 只要稍加修改即可:

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点,返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) { 
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点,需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

具体的区别:

1、 base case 变为 n == 1 , 反转⼀个元素, 就是它本⾝, 同时要记录后驱
节点。

2、 刚才我们直接把 head.next 设置为 null, 因为整个链表反转后原来的head 变成了整个链表的最后⼀个节点。 但现在 head 节点在递归反转之后不⼀定是最后⼀个节点了, 所以要记录后驱 successor (第 n + 1 个节点) , 反转之后将 head 连接上。

在这里插入图片描述

三、 反转链表的⼀部分

现在解决我们最开始提出的问题, 给⼀个索引区间 [m,n] (索引从 1 开始) , 仅仅反转区间中的链表元素

ListNode reverseBetween(ListNode head, int m, int n)

⾸先, 如果 m == 1 , 就相当于反转链表开头的 n 个元素嘛, 也就是我们刚才实现的功能:

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        // 相当于反转前 n 个元素
        return reverseN(head, n);
    }
    // ...
}

如果 m != 1 怎么办?如果我们把 head 的索引视为 1,那么我们是想从第 m 个元素开始反转对吧;如果把 head.next 的索引视为 1 呢?那么相对于 head.next,反转的区间应该是从第 m - 1 个元素开始的;那么对于 head.next.next 呢……

区别于迭代思想,这就是递归思想,所以我们可以完成代码:

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

四、 最后总结

递归的思想相对迭代思想, 稍微有点难以理解, 处理的技巧是: 不要跳进递归, ⽽是利⽤明确的定义来实现算法逻辑。

递归操作链表并不⾼效。 和迭代解法相⽐, 虽然时间复杂度都是 O(N), 但是迭代解法的空间复杂度是 O(1), ⽽递归解法需要堆栈, 空间复杂度是 O(N)

0

评论区