剑指 Offer 06. 从尾到头打印链表（Easy）
题目描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。限制：0 <= 链表长度 <= 10000。
举例说明
示例 1：
输入：head = [1,3,2]。输出：[2,3,1]。
解题思路
利用递归：先走至链表末端，回溯时依次将节点值加入列表，这样就可以实现链表值的倒序输出。算法流程：
递推阶段：每次传入 head.next，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。回溯阶段：层层回溯时，将当前节点值加入列表，即 temp.add(head.val)。最终，将列表 temp 转化为数组 res ，并返回即可。 代码示例：class Solution {
List
public int[] reversePrint(ListNode head) {
reverse(head);
int[] res = new int[temp.size()];
for (int i = 0; i < res.length; i++) {
res[i] = temp.get(i);
}
return res;
}
private void reverse(ListNode head) {
if (head == null) {
return;
}
reverse(head.next);
temp.add(head.val);
}
}
复杂度分析：
时间复杂度 O(N)： 遍历链表，递归 N 次。空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间。
剑指 Offer 24. 反转链表（Easy）
题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。限制：0 <= 节点个数 <= 5000。
举例说明
示例：
输入: 1->2->3->4->5->NULL。输出: 5->4->3->2->1->NULL。
解题思路
算法流程：
定义两个指针：pre 和 cur。pre 在前 cur 在后。每次让 pre 的 next 指向 cur，实现一次局部反转。局部反转完成之后，pre 和 cur 同时往前移动一个位置。循环上述过程，直至 pre 到达链表尾部。 代码示例：class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
复杂度分析：
时间复杂度 O(N)： 遍历链表使用线性大小时间。空间复杂度 O(1)： 变量 pre 和 cur 使用常数大小额外空间。
剑指 Offer 35. 复杂链表的复制（Medium）
题目描述
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。限制：
-10000 <= Node.val <= 10000。Node.random 为空（null）或指向链表中的节点。节点数目不超过 1000。
举例说明
示例 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。
解题思路
利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。算法流程：
若头节点 head 为空节点，直接返回 null；初始化：哈希表 map，节点 cur 指向头节点；复制链表：
建立新节点，并向 map 添加键值对 (原 cur 节点, 新 cur 节点）；cur 遍历至原链表下一节点； 构建新链表的引用指向：
构建新节点的 next 和 random 引用指向；cur 遍历至原链表下一节点； 返回值：新链表的头节点 map[head]； 代码示例：class Solution {
public Node copyRandomList(Node head) {
Map
Node cur = head;
while (cur != null) {
if (!map.containsKey(cur)) {
map.put(cur, new Node(cur.val));
}
cur = cur.next;
}
cur = head;
while (cur != null) {
if (cur.next != null) {
map.get(cur).next = map.get(cur.next);
}
if (cur.random != null) {
map.get(cur).random = map.get(cur.random);
}
cur = cur.next;
}
return map.get(head);
}
}
复杂度分析：
时间复杂度 O(N)：两轮遍历链表，使用 O(N) 时间。空间复杂度 O(N)： 哈希表 map 使用线性大小的额外空间。
推荐链接
发表评论