day2 题目：剑指 Offer 06. 从尾到头打印链表、剑指 Offer 24. 反转链表、剑指 Offer 35. 复杂链表的复制

知识点：链表、递归、哈希，难度为简单、中等、中等

学习计划链接：「剑指 Offer」 - 学习计划

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入： head = [1,3,2]
输出： [2,3,1]

限制：

0 <= 链表长度 <= 10000

思路及代码

反过来输出，那就用栈，后进先出。

/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function (head) {
  let res = [];
  while (head) {
    res.unshift(head.val);
    head = head.next;
  }
  return res;
};

剑指 Offer 24. 反转链表

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

示例:

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

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

思路及代码

老题目了，第三次做，在遍历链表时，将当前节点的 nowp 指针改为指向前一个节点 prev，最后返回新的链表头 prep。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prep = null;
  let nowp = head;
  while (nowp) {
    let t = nowp.next;
    nowp.next = prep;
    prep = nowp;
    nowp = t;
  }
  return prep;
};

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入： head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出： [[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入： head = [[1,1],[2,1]]
输出： [[1,1],[2,1]]

示例 3：

输入： head = [[3,null],[3,0],[3,null]]
输出： [[3,null],[3,0],[3,null]]

示例 4：

输入： head = []
输出： []
解释： 给定的链表为空（空指针），因此返回 null。

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

注意： 本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

思路及代码

1、利用 map 存储拷贝过的结点

并且递归的进行拷贝，如果当前节点被拷贝过则直接返回拷贝后的节点指针

var m = new Map();
/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
  if (!head) return null;
  if (m.has(head)) return m.get(head);
  let newv = new Node(head.val, null, null);
  m.set(head, newv);
  newv.next = copyRandomList(head.next);
  newv.random = copyRandomList(head.random);
  return newv;
};

2、迭代，拆分节点

这个是看题解发现的思路，将该链表中每一个节点拆分为两个相连的节点，对于任意一个原节点 S，其拷贝节点 S′ 即为其后继节点，然后将新节点的 random 正确赋值，再将新链表的 next 正确赋值。

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
  if (!head) return null;
  let nowp = head;
  for (let nowp = head; nowp; nowp = nowp.next.next) {
    let t = new Node(nowp.val, nowp.next, null);
    nowp.next = t;
  }
  for (let nowp = head; nowp; nowp = nowp.next.next) {
    nowp.next.random = nowp.random ? nowp.random.next : null; // 新链表的random赋值
  }
  let res = head.next;
  for (let nowp = head; nowp; nowp = nowp.next) {
    let newNode = nowp.next;
    nowp.next = newNode.next;
    newNode.next = newNode.next ? nowp.next.next : null; // 新链表的next赋值
  }
  return res;
};