一、反转链表

  1. var reverseList = function(head) {
  2.     if (head == null || head.next == null) {
  3.         return head;
  4.     }
  5.     const last = reverseList(head.next);
  6.     head.next.next = head;
  7.     head.next = null;
  8.     return last;
  9. };

二、反转前n部分

  1. let successor = null; // 后驱节点
  3. let reverseListN = function(head, n) {
  4.     if (n === 1) {
  5.         // 记录第 n + 1 个节点
  6.         successor = head.next;
  7.         return head;
  8.     }
  10.     // 以 head.next 为起点，需要反转前 n - 1 个节点
  11.     let last = reverseListN(head.next, n - 1);
  13.     head.next.next = head;
  15.     // 让反转之后的 head 节点和后面的节点连起来
  16.     head.next = successor;
  17.     return last;
  18. };

三、反转(m, n)

  1. let successor = null; // 后驱节点
  3. let reverseListN = function(head, n) {
  4.     if (n === 1) {
  5.         // 记录第 n + 1 个节点
  6.         successor = head.next;
  7.         return head;
  8.     }
  10.     // 以 head.next 为起点，需要反转前 n - 1 个节点
  11.     let last = reverseListN(head.next, n - 1);
  13.     head.next.next = head;
  15.     // 让反转之后的 head 节点和后面的节点连起来
  16.     head.next = successor;
  17.     return last;
  18. };
  20. /**
  21.  * @param {ListNode} head
  22.  * @param {number} m
  23.  * @param {number} n
  24.  * @return {ListNode}
  25.  */
  26. let reverseBetween = function(head, m, n) {
  27.     // base case
  28.     if (m === 1) {
  29.         return reverseListN(head, n);
  30.     }
  31.     // 前进到反转的起点触发 base case
  32.     head.next = reverseBetween(head.next, m - 1, n - 1);
  33.     return head;
  34. };