LeetCode刷题计划（Day 2） leetcode

回顾链表

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」。

文章图片

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

问题描述：
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例1：

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

限制：
- 0 <= 链表长度 <= 1000
【LeetCode刷题计划（Day 2）】解题思路：
遍历链表时逆序保存节点的值：

/** * Definition for singly-linked list. * type ListNode struct { *Val int *Next *ListNode * } */ func reversePrint(head *ListNode) []int { if head == nil { return nil } res := []int{} for cur := head; cur != nil; cur = cur.Next { res = append([]int{cur.Val}, res...) } return res }

剑指 Offer 24. 反转链表

剑指 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 = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。

提示：
- -10000 <= Node.val <= 10000
- Node.random 为空（null）或指向链表中的节点
- 节点数目不超过 1000
解题思路：
维护一个哈希表，第一次遍历老链表时，保存新老链表各节点的映射；第二次遍历老链表时利用哈希表，给新链表节点的指针进行赋值：

/** * Definition for a Node. * type Node struct { *Val int *Next *Node *Random *Node * } */ func copyRandomList(head *Node) *Node { nodeMap := make(map[*Node]*Node) for cur := head; cur != nil; cur = cur.Next { newNode := &Node{Val: cur.Val} nodeMap[cur] = newNode } for cur := head; cur != nil; cur = cur.Next { nodeMap[cur].Next = nodeMap[cur.Next] nodeMap[cur].Random = nodeMap[cur.Random] } return nodeMap[head] }