剑指offer day2 链表（简单）

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

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

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

题目	知识点	难度
剑指 Offer 06. 从尾到头打印链表	栈、递归、链表	简单
剑指 Offer 24. 反转链表	递归、链表	中等
剑指 Offer 35. 复杂链表的复制	哈希表、链表	中等

剑指 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
};