• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

开发技术 开发技术 3周前 (09-05) 24次浏览

一、反转整个链表

问题:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 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为起点的链表反转,并返回反转之后的头节点。

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

明白了函数的定义后,在来看这个问题。比如我们想反转这个链表

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

那么输入reverse(head)后,会在ListNode ret = reverse(head.next);进行递归

不要跳进递归!(你的脑袋能压几个栈呀?)

根据reverse函数的定义,函数调用后会返回反转之后的头节点,我们用变量ret接收

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转现在再来看一下代码

head.next.next = head;

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

接下来:

head.next = null;
return ret;

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

再跳出这层递归就会得到:

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

神不神奇,这样整个链表就反转过来了!

递归代码就是这么简洁优雅,但要注意两个问题:

1、递归函数要有base case,不然就会一直递归,导致栈溢出

if (head == null || head.next == null) return head;

即链表为空或只有一个节点,直接返回

2、当链表递归反转后,新的头节点为ret,而head变成了最后一个节点,应该令链表的某尾指向null

head.next = null;

理解这两个问题之后,我们可以进一步深入研究链表反转的问题,接下来的问题其实均为在这个算法上的扩展。

二、反转链表前N个节点

接下来我们来看这个问题:

问题:反转链表前N个节点,并返回链表头节点

说明:1 <= N <= 链表长度

示例:

输入: 1->2->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连接上。

利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

OK,如果这个函数你也能看懂,就离实现反转一部分链表不远了。

三、反转链表的一部分

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

说明:1 <= m <= n <= 链表长度

示例:

输入: 1->2->3->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!


喜欢 (0)