Code More Create

Appearance

Return to top
On this page

反转链表的一部分

什么叫反转单链表的一部分

就是给你一个索引区间，让你把单链表中这部分元素反转，其他部分不变：

递归反转整个链表 

/*
 * @lc app=leetcode.cn id=206 lang=java
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode last = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return last;
  }
}
// @lc code=end

只能说非常妙！

反转链表前 N 个节点 

 public ListNode reserveN(ListNode head, int n) {
    if (n == 1) {
      successor = head.next;
      return head;
    }
    ListNode last = reserveN(head.next, n - 1);
    head.next.next = head;
    head.next = successor;
    return last;
  }

具体的区别：

  1. base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
  2. 刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

反转链表的一部分 

import java.util.List;

/*
 * @lc app=leetcode.cn id=92 lang=java
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  ListNode successor = null; // 记录
	// 反转前n个结点，返回的是新的头结点
  public ListNode reserveN(ListNode head, int n) {
    if (n == 1) {
      successor = head.next;
      return head;
    }
    // last 表示反转部分的最后一个结点，也是新的头结点
    ListNode last = reserveN(head.next, n - 1);
    head.next.next = head;
    head.next = successor;
    return last;
  }

  public ListNode reverseBetween(ListNode head, int left, int right) {
    if (left == 1) {
      return reserveN(head, right);
    }
    head.next = reverseBetween(head.next, left - 1, right - 1);
    return head;
  }
}
// @lc code=end

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

处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。

值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。