反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
转载labuladong的题解 这个问题其实是在“递归反转链表”这个算法上的扩展。
递归反转整个链表:
ListNode reverse(ListNode head) { if (head.next == null) return head; ListNode last = reverse(head.next); head.next.next = head; head.next = null; return last; }这次我们实现一个这样的函数:
// 将链表的前 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 连接上。 OK,如果这个函数你也能看懂,就离实现「反转一部分链表」不远了。
现在解决我们最开始提出的问题,给一个索引区间 [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; }至此,我们的最终大 BOSS 就被解决了。
递归的思想相对迭代思想,稍微有点难以理解,处理的技巧是:不要跳进递归,而是利用明确的定义来实现算法逻辑。
处理看起来比较困难的问题,可以尝试化整为零,把一些简单的解法进行修改,解决困难的问题。
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗:37.3 MB, 在所有 Java 提交中击败了8.70%的用户