反转链表 (opens new window)

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

记录一个 next 表示下一个节点， cur 表示当前节点，prev 表示上一个节点， 在循环中不断的把 cur.next 赋值为 prev，然后 cur 前进为刚刚保存的 next 节点，直到 cur 为 null。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while(curr) {
      let next = curr.next
      curr.next = prev
      prev = curr
      curr = next
    }
    return prev
};

时间复杂度：O(n)，空间复杂度：O(1)

• 递归

var reverseList = function(head) {
  // 递归结束条件
  if (head === null || head.next === null) { // base  case
    return head
  }

  // 递归反转 子链表
  let last = reverseList(head.next)
  // 调整原来头结点和第2个节点的指向
  head.next.next = head
  head.next = null // 当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null

  // 将调整后的链表返回
  return last
}

反转链表前N个节点

// 将链表的前 n 个节点反转（n <= 链表长度）
function reverseN(head, n) {
  var curr = head;
  var prev = null;
  for (var i = 0; i < n; i++) {
    var next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  head.next = curr; // 在现在的head接下去
  return prev;
}

// 递归
var successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
function reverseN(head, n) {
  if (n == 1) {
    // 记录第 n + 1 个节点
    successor = head.next;
    return head;
  }
  // 以 head.next 为起点，需要反转前 n - 1 个节点
  var last = reverseN(head.next, n - 1);

  head.next.next = head;
  // 让反转之后的 head 节点和后面的节点连起来
  head.next = successor;
  return last;
}

反转链表一部分

给一个索引区间 [m, n]（索引从 1 开始），仅仅反转区间中的链表元素。

var reverseBetween = function(head, m, n) {
  // base case
  if(m === 1) {
    // 反转以head开头的n个节点
    return reverseN(head, n);
  }
  // 将head.next作为起点反转前m-1个节点
  head.next = reverseBetween(head.next, m - 1, n - 1);
  return head;
}