LeetCode-206.反转链表

haiweilian2021-03-12算法LeetCode

题目描述

反转一个单链表。

示例 1：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解法一之迭代

在遍历链表时，让当前的节点的指针指向上一个节点，因为当前节点指向了上一个节点切断了链表的引用，所有还要提前存储当前节点之后的节点

举例如有链表 head = 1->2->3->null。我们需要定义三个变量来实现反转。

pre 上一个节点，默认 pre = null。
cur 当前遍历的节点，默认 cur = head(1->2->3->null)。
next 保存剩余的节点，默认 next = null。

以下为执行过程

第一次反转，当前为 1。

需要先保存当前节点之后的所有节点 next = cur.next，结果为 next = 2->3->null。
让当前节点的指针指向上一个节点 cur.next = pre，结果为 cur = 1->null。注意这时已经切断了当前的链表，所以才需要使用 next 保存。
让当前节点变为上一个节点 pre = cur，结果为 pre = 1->null。
这样就完成了第一次反转，剩余的节点继续遍历 cur = next，结果为 cur = 2->3->null。

第二次反转，当前为 2。

需要先保存当前节点之后的所有节点 next = cur.next，结果为 next = 3->null。
让当前节点的指针指向上一个节点 cur.next = pre，结果为 cur = 2->1->null。
让当前节点变为上一个节点 pre = cur，结果为 pre = 2-1->null。
这样就完成了第一次反转，剩余的节点继续遍历 cur = next，结果为 cur = 3->null。

第三次反转，当前为 3。

需要先保存当前节点之后的所有节点 next = cur.next，结果为 next = null。
让当前节点的指针指向上一个节点 cur.next = pre，结果为 cur = 4-2->1->null。
让当前节点变为上一个节点 pre = cur，结果为 pre = 3-2-1->null。
这样就完成了第一次反转，剩余的节点继续遍历 cur = next，结果为 cur = null。

第三次反转，当前为 null，结束遍历，返回最终的结果 pre。

代码实现

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

  while (cur) {
    // 保存下一个节点
    next = cur.next;
    // 让当前节点的指针指向上一个节点
    cur.next = pre;
    // 让当前节点变为上一个节点
    pre = cur;
    // 重置当前节点
    cur = next;
  }

  // 解构赋值，和上面逻辑一样。
  // while (cur) {
  //   ;[cur.next, pre, cur] = [pre, cur, cur.next]
  // }

  return pre;
};
// @lc code=end

// ===================================================================
// ========================== @test ==================================
// ===================================================================
let ListNode = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: null,
    },
  },
};

function print(head) {
  let cur = head;
  let link = [];
  while (cur) {
    link.push(cur.val);
    cur = cur.next;
  }
  return `长度为 ${link.length} : 值为 ${link.join("->")}`;
}

console.log(print(reverseList(ListNode))); // 长度为 3 : 值为 3->2->1

LeetCode-206.反转链表

题目描述

解法一之迭代

ON THIS PAGE