当前位置:网站首页>链表(简单)
链表(简单)
2022-07-05 13:48:00 【安娜和她的笔记本】
剑指 Offer 06. 从尾到头打印链表
剑指 Offer 24. 反转链表
剑指 Offer 35. 复杂链表的复制
剑指 Offer 06. 从尾到头打印链表 - 力扣(LeetCode)
单链表的定义:
/*Definition for singly-linked list:*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
一:栈方法
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack=new Stack<>();
ListNode cur=head;
while(cur!=null){
stack.push(cur);
cur=cur.next;
}
int[] arr=new int[stack.size()];
for(int i=0;i<arr.length;i++){
arr[i]=stack.pop().val;
}
return arr;
}
}
/** 复杂度分析: 时间复杂度 O(N) 空间复杂度 O(N) */
class Solution {
public int[] reversePrint(ListNode head) {
LinkedList<Integer> stack = new LinkedList<Integer>();
while(head != null) {
stack.addLast(head.val);//addLast()方法用于在LinkedList的末尾插入特定元素
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i++)
res[i] = stack.removeLast();//removeLast()方法用于从LinkedList中删除最后一个元素
return res;
}
}
/** 复杂度分析: 时间复杂度 O(N):入栈和出栈共使用O(N)时间。 空间复杂度 O(N):辅助栈stack和数组res共使用O(N)的额外空间 */
二:递归法
算法流程:
- 递推阶段: 每次传入 head.next ,以 head == null(即走过链表尾部节点)为递归终止条件,此时直接返回。
- 回溯阶段: 层层回溯时,将当前节点值加入列表,即tmp.add(head.val)。
最终,将列表 tmp 转化为数组 res ,并返回即可。
复杂度分析
- 时间复杂度 O(N): 遍历链表,递归 N 次。
- 空间复杂度 O(N):系统递归需要使用 O(N) 的栈空间。
class Solution {
ArrayList<Integer> tmp = new ArrayList<Integer>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[tmp.size()];
for(int i = 0; i < res.length; i++)
res[i] = tmp.get(i);
return res;
}
void recur(ListNode head) {
if(head == null) return;
recur(head.next);
tmp.add(head.val);
}
}
三:
class Solution {
// 执行用时 : 0 ms, 在所有 Java 提交中击败了 100.00% 的用户
// 内存消耗 : 39.8 MB, 在所有 Java 提交中击败了 100.00% 的用户
// 不使用栈,不使用递归,反正怎么样也是扫描两趟,为什么要额外分配空间呢?
public static int[] reversePrint(ListNode head) {
ListNode node = head;
int count = 0;
while (node != null) {
++count;
node = node.next;
}
int[] nums = new int[count];
node = head;
for (int i = count - 1; i >= 0; --i) {
nums[i] = node.val;
node = node.next;
}
return nums;
}
}
剑指 Offer 24. 反转链表 - 力扣(LeetCode)
一:迭代
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode pre=null;
ListNode cur=head;
ListNode tmp=null;
while(cur!=null){
tmp=cur.next;// 暂存后继节点 cur.next
cur.next=pre;// 修改 next 引用指向
pre=cur;// pre 暂存 cur
cur=tmp;// cur 访问下一节点
}
return pre;
}
}
二:递归
class Solution {
public ListNode reverseList(ListNode head) {
return recur(head, null); // 调用递归并返回
}
private ListNode recur(ListNode cur, ListNode pre) {
if (cur == null){
return pre; // 终止条件
}
ListNode res = recur(cur.next, cur); // 递归后继节点
cur.next = pre; // 修改节点引用指向
return res; // 返回反转链表的头节点
}
}
剑指 Offer 35. 复杂链表的复制 - 力扣(LeetCode)
一:哈希表
/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> m = new HashMap<>();
Node p = head;
while(head != null) {
Node t = new Node(head.val);
m.put(head, t);
head = head.next;
}
head = p;
//根据原链表,查找哈希表将新链表连起来
while(head != null) {
Node n = head.next; //原始节点的下一个节点
Node r = head.random;//原始节点随机节点
//新节点的next指向下一个新节点
m.get(head).next = m.get(n);
//设置新节点的random结点指向
m.get(head).random = m.get(r);
head = head.next;
}
return m.get(p);
}
}
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
Map<Node, Node> map = new HashMap<>();
//复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
//构建新链表的 next 和 random 指向
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
//返回新链表的头节点
return map.get(head);
}
}
边栏推荐
- Ordering system based on wechat applet
- Flutter 3.0更新后如何应用到小程序开发中
- 嵌入式软件架构设计-消息交互
- 【MySQL 使用秘籍】一網打盡 MySQL 時間和日期類型與相關操作函數(三)
- Zhubo Huangyu: these spot gold investment skills are not really bad
- kafaka 日志收集
- 【MySQL 使用秘籍】一网打尽 MySQL 时间和日期类型与相关操作函数(三)
- Kotlin协程利用CoroutineContext实现网络请求失败后重试逻辑
- leetcode 10. Regular expression matching regular expression matching (difficult)
- The "Baidu Cup" CTF competition was held in February 2017, Web: explosion-2
猜你喜欢
What are the private addresses
STM32 reverse entry
Idea设置方法注释和类注释
Binder communication process and servicemanager creation process
运筹说 第68期|2022年最新影响因子正式发布 快看管科领域期刊的变化
ZABBIX monitoring
C object storage
Catch all asynchronous artifact completable future
Laravel框架运行报错:No application encryption key has been specified
Network security - Novice introduction
随机推荐
私有地址有那些
The development of speech recognition app with uni app is simple and fast.
MySQL - database query - sort query, paging query
那些考研后才知道的事
What are the private addresses
MySQL get time
PHP generate Poster
Aspx simple user login
The "Baidu Cup" CTF competition was held in February 2017, Web: explosion-2
Could not set property ‘id‘ of ‘class XX‘ with value ‘XX‘ argument type mismatch 解决办法
redis6数据类型及操作总结
2022年机修钳工(高级)考试题模拟考试题库模拟考试平台操作
Pancake Bulldog robot V2 (code optimized)
Jetpack compose introduction to mastery
4年工作经验,多线程间的5种通信方式都说不出来,你敢信?
53. 最大子数组和:给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
leetcode 10. Regular Expression Matching 正则表达式匹配 (困难)
Hide Chinese name
The real king of caching, Google guava is just a brother
Personal component - message prompt