题目
剑指 Offer 24. 反转链表 - 力扣（LeetCode）
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 复制代码
分析一
首先链表题，那么大概率要么是用迭代，要么是用递归
如果使用迭代，那么需要在遍历的同时创建一个新的链表，将每个节点的指向从后往前指，依次连接起来
实现
function reverseList(head: ListNode | null): ListNode | null { let prev = null let cur = head while(cur) { const next = cur.next cur.next = prev prev = cur cur = next } return prev }; 复制代码
分析二
如果使用递归，需要考虑递推公式如何实现
开始的时候很多同学对如何倒转链表的理解不是很清晰，那么我们先从简单的链表入手，以伪代码的形式，来看看如何实现简单的链表倒转，再到最终的实现一个通用的方法
- 递归
假设有一个方法 f 可以表示置换两个节点的顺序
即：若1→ 2→ 3→null
则：
f(1) = 3→2→1
f(2) = 3→2
那么
f(1) = f(2) → 1 f(1) = f(3) → 2 → 1
实现
function reverseList(head: ListNode | null): ListNode | null { let result: ListNode | null = null function handle(node: ListNode | null) { if (!node) { return } handle(node.next) result = node } handle(head) return result }; 复制代码
题目
剑指 Offer 35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 复制代码
分析
首先，本题属于中等难度，对于基础不好的同学还是比较有挑战性的
那么开始分析
如果只是一个简单链表的复制，那本题就简单多了，只需要迭代创建新节点依次连接起来，就可以实现链表的复制
现在的难点在于出现了一个任意指向的指针需要复制，那么就会出现这种情况
如果在第一次迭代时，就复制任意指针节点，可能会出现新的目标节点还未创建的情况
所以这道题的解答步骤有三
- 首先复制简单链表，作为我们最终返回的结果
- 在复制迭代的过程中，建立旧节点和新节点的对应关系，用于后续使用旧节点查询新节点
- 在进行一次迭代，利用对应关系，把新链表每个节点的任意指针维护上去，即得到我们想要的复制链表了
对了，做的时候疏忽，记得加上链表为空时的判断
实现
/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; */ /** * @param {Node} head * @return {Node} */ var copyRandomList = function(head) { if (!head) return head let oldHead = head let newHead = new Node() let newNode = newHead const map = new Map() while(oldHead){ newNode.val = oldHead.val newNode.next = oldHead.next ? new Node() : null map.set(oldHead, newNode) newNode = newNode.next oldHead = oldHead.next } newNode = newHead while(head) { newNode.random = head.random ? map.get(head.random) : null newNode = newNode.next head = head.next } return newHead };
