title

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Analyze

prev  cur  next
        1 -> 2 -> 3 -> 4 -> 5 -> null
null <- 1 -> 2 -> 3 -> 4 -> 5

step:

1. 定义三个变量 prev, cur, next 表示上一个值, 当前值, 下一个值;
2. 如果存在 cur.next 则将 cur.next 指向 prev;
3. 将 cur 移动到 next 位置, prev 移动到 cur 位置, 重复步骤 2;

/**
 * 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 cur = head
  if (head) {
    let next = head.next
    while (cur.next) {
      cur.next = prev
      prev = cur
      cur = next
      next = next.next
    }
    cur.next = prev
  }
  return cur
};

这样写存在一些冗余的代码, 比如需要判断 head 是否为空, 同时因为 while 中的条件是 cur.next, 因为末尾的 cur.next 需要单独处理一遍, 比较麻烦, 因此进而优化。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  let prev = null
  let cur = head
  while (cur !== null) {
    let next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
};

根据题目的建议, 接着用递归的方式实现一遍(值得注意的是, 迭代与递归的写法都是能互相转换的。)

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  let prev = null
  let cur = head

  const recursiveFn = () => {
    if (cur === null) return

    let next = cur.next
    cur.next = prev
    prev = cur
    cur = next

    recursiveFn()
  }
  recursiveFn()
  return prev
};

Sister Title

92