利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转 |
您所在的位置:网站首页 › 反转链表的一部分 › 利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转 |
一、反转整个链表
问题:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL //单链表的实现结构 public class ListNode { int val; ListNode next; ListNode(int x) { val = x;} }反转链表利用迭代不难实现,如果使用递归则有些许难度。 首先来看源码实现: ListNode reverse(ListNode head) { if(head == null || head.next == null) return head; ListNode ret = reverse(head.next); head.next.next = head; head.next = null; return ret; }是否看起来不知所云,而又被这如此简洁的代码所震撼?让我们一起探索一下其中的奥秘。 对于递归算法,最重要的是明确递归函数的定义。 我们的reverse函数的定义如下: 输入一个节点head,将以head为起点的链表反转,并返回反转之后的头节点。 明白了函数的定义后,在来看这个问题。比如我们想反转这个链表 那么输入reverse(head)后,会在ListNode ret = reverse(head.next);进行递归 不要跳进递归!(你的脑袋能压几个栈呀?) 根据reverse函数的定义,函数调用后会返回反转之后的头节点,我们用变量ret接收 现在再来看一下代码 head.next.next = head; 接下来: head.next = null; return ret;再跳出这层递归就会得到: 神不神奇,这样整个链表就反转过来了! 递归代码就是这么简洁优雅,但要注意两个问题: 1、递归函数要有base case,不然就会一直递归,导致栈溢出 if (head == null || head.next == null) return head; 即链表为空或只有一个节点,直接返回 2、当链表递归反转后,新的头节点为ret,而head变成了最后一个节点,应该令链表的某尾指向null head.next = null; 理解这两个问题之后,我们可以进一步深入研究链表反转的问题,接下来的问题其实均为在这个算法上的扩展。 二、反转链表前N个节点接下来我们来看这个问题: 问题:反转链表前N个节点,并返回链表头节点 说明:1 3->4->5->NULL, n = 4 输出: 4->3->2->1->5->NULL 解决思路和反转整个链表差不多,只需稍加修改 ListNode successor = null; // 后驱节点(第 n + 1 个节点) ListNdoe reverseN(ListNode head, int n) { if (n == 1) { successor = head.next; return head; } // 以 head.next 为起点,需要反转前 n - 1 个节点 ListNode ret = reverseN(head.next, n - 1); head.next.next = head; head.next = successor; // 将反转后的 head 与后面节点连接 return ret; }具体区别: 1、base case 变为n == 1, 同时需要记录后驱节点。 2、之前把head.next 设置为null,因为整个链表反转后,head变为最后一个节点。 现在head节点在递归反转后不一定为最后一个节点,故应记录后驱successor(第 n + 1 个节点), 反转之后将head连接上。 OK,如果这个函数你也能看懂,就离实现反转一部分链表不远了。 三、反转链表的一部分现在我们开始解决这个问题,给一个索引区间[m, n](索引从1开始),仅仅反转区间中的链表元素。 说明:1 4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 猛一看很难想到思路。 试想一下,如果m == 1,就相当于反转链表的前 n 元素嘛,也就是我们刚才实现的功能: ListNode reverseBetween(ListNode head, int m, int n) { //base case if (m == 1) { return reverseN(head, n); // 相当于反转前 n 个元素 } // ... }那如果m != 1 该怎么办? 如果把head的索引视为1,那么我们是想从第m个元素开始反转; 如果把head.next的索引视为1,那么我们是想从第m - 1 个元素开始反转; 如果把head.next.next的索引视为1,那么我们是想从第m - 2 个元素开始反转; ...... 区别于迭代思想,这就是递归的思想,所以我们可以完成代码: ListNode reverseBetween(ListNode head, int m, int n) { // base case if (m == 1) { return reverseN(head, n); } // 递归前进到触发 base case (m == 1) head.next = reverseBetween(head.next, m - 1, n - 1); return head; }至此,我们终于干掉了大BOSS! |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |