当前位置:网站首页>鏈錶(簡單)
鏈錶(簡單)
2022-07-05 13:49: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);
}
}
边栏推荐
- 49. Grouping of alphabetic ectopic words: give you a string array, please combine the alphabetic ectopic words together. You can return a list of results in any order. An alphabetic ectopic word is a
- Idea set method annotation and class annotation
- RK3566添加LED
- js 从一个数组对象中取key 和value组成一个新的对象
- With 4 years of working experience, you can't tell five ways of communication between multithreads. Dare you believe it?
- Prefix, infix, suffix expression "recommended collection"
- 49. 字母异位词分组:给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
- Basic characteristics and isolation level of transactions
- Log4j utilization correlation
- PHP generate Poster
猜你喜欢
Idea set method annotation and class annotation
Kotlin collaboration uses coroutinecontext to implement the retry logic after a network request fails
:: ffff:192.168.31.101 what address is it?
不知道这4种缓存模式,敢说懂缓存吗?
搭建一个仪式感点满的网站,并内网穿透发布到公网 2/2
ZABBIX monitoring
Elfk deployment
The real king of caching, Google guava is just a brother
Nantong online communication group
面试官灵魂拷问:为什么代码规范要求 SQL 语句不要过多的 join?
随机推荐
Binder communication process and servicemanager creation process
Apicloud studio3 WiFi real machine synchronization and WiFi real machine preview instructions
53. Maximum subarray sum: give you an integer array num, please find a continuous subarray with the maximum sum (the subarray contains at least one element) and return its maximum sum.
asp.net 读取txt文件
【 script secret pour l'utilisation de MySQL 】 un jeu en ligne sur l'heure et le type de date de MySQL et les fonctions d'exploitation connexes (3)
那些考研后才知道的事
Internal JSON-RPC error. {"code":-32000, "message": "execution reverted"} solve the error
Solve the problem of invalid uni app configuration page and tabbar
几款分布式数据库的对比
Summit review | baowanda - an integrated data security protection system driven by compliance and security
aspx 简单的用户登录
【MySQL 使用秘籍】一网打尽 MySQL 时间和日期类型与相关操作函数(三)
Win10——轻量级小工具
NFT value and white paper acquisition
The real king of caching, Google guava is just a brother
Usage, installation and use of TortoiseSVN
Aikesheng sqle audit tool successfully completed the evaluation of "SQL quality management platform grading ability" of the Academy of communications and communications
MMSeg——Mutli-view时序数据检查与可视化
With 4 years of working experience, you can't tell five ways of communication between multithreads. Dare you believe it?
研究生可以不用学英语?只要考研英语或六级分数高!