当前位置:网站首页>Linked list (simple)
Linked list (simple)
2022-07-05 13:50:00 【Anna and her notebook】
The finger of the sword Offer 06. Print linked list from end to end
The finger of the sword Offer 24. Reverse a linked list
The finger of the sword Offer 35. Replication of complex linked list
The finger of the sword Offer 06. Print linked list from end to end - Power button (LeetCode)
Definition of a single linked list :
/*Definition for singly-linked list:*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
One : Stack method
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;
}
}
/** Complexity analysis : Time complexity O(N) Spatial complexity O(N) */
class Solution {
public int[] reversePrint(ListNode head) {
LinkedList<Integer> stack = new LinkedList<Integer>();
while(head != null) {
stack.addLast(head.val);//addLast() Method is used in LinkedList Insert a specific element at the end of
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i++)
res[i] = stack.removeLast();//removeLast() Method is used to get from LinkedList Delete the last element in
return res;
}
}
/** Complexity analysis : Time complexity O(N): Stack in and stack out are used together O(N) Time . Spatial complexity O(N): Auxiliary stack stack And an array res Use together O(N) Extra space */
Two : Recursive method
Algorithm flow :
- Recurrence stage : Every time I pass in head.next , With head == null( That is, walk through the tail node of the linked list ) Is a recursive termination condition , Go straight back to .
- Backtracking phase : When you go back layer by layer , Add the current node value to the list , namely tmp.add(head.val).
Final , Will list tmp Convert to array res , And return .
Complexity analysis
- Time complexity O(N): Traversing the linked list , recursive N Time .
- Spatial complexity O(N): System recursion needs to use O(N) Stack space of .
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);
}
}
3、 ... and :
class Solution {
// Execution time : 0 ms, In all Java Defeated in submission 100.00% Users of
// Memory consumption : 39.8 MB, In all Java Defeated in submission 100.00% Users of
// No stack , Do not use recursion , Anyway, it is also scanned twice , Why allocate extra space ?
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;
}
}
The finger of the sword Offer 24. Reverse a linked list - Power button (LeetCode)
One : iteration
/** * 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;// Staging successor nodes cur.next
cur.next=pre;// modify next Reference point
pre=cur;// pre The staging cur
cur=tmp;// cur Visit the next node
}
return pre;
}
}
Two : recursive
class Solution {
public ListNode reverseList(ListNode head) {
return recur(head, null); // Call recursion and return
}
private ListNode recur(ListNode cur, ListNode pre) {
if (cur == null){
return pre; // Termination conditions
}
ListNode res = recur(cur.next, cur); // Recursive successor node
cur.next = pre; // Modify the node reference to
return res; // Returns the header node of the inverted linked list
}
}
The finger of the sword Offer 35. Replication of complex linked list - Power button (LeetCode)
One : Hashtable
/* // 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;
// According to the original linked list , Look up the hash table and connect the new linked list
while(head != null) {
Node n = head.next; // The next node of the original node
Node r = head.random;// Original node random node
// New nodes next Point to the next new node
m.get(head).next = m.get(n);
// Set the new node's random The node points to
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<>();
// Copy each node , And establish “ Original node -> New node ” Of Map mapping
while(cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
// To build a new linked list next and random Point to
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
// Return the head node of the new linked list
return map.get(head);
}
}
边栏推荐
- Assembly language - Beginner's introduction
- Jasypt configuration file encryption | quick start | actual combat
- Wonderful express | Tencent cloud database June issue
- How to deal with the Yellow Icon during the installation of wampserver
- Etcd database source code analysis -- rawnode simple package
- 我为什么支持 BAT 拆掉「AI 研究院」
- Binder communication process and servicemanager creation process
- 【云资源】云资源安全管理用什么软件好?为什么?
- With 4 years of working experience, you can't tell five ways of communication between multithreads. Dare you believe it?
- aspx 简单的用户登录
猜你喜欢
南理工在线交流群
Operational research 68 | the latest impact factors in 2022 were officially released. Changes in journals in the field of rapid care
Set up a website with a sense of ceremony, and post it to the public 2/2 through the intranet
锚点导航小demo
How to apply the updated fluent 3.0 to applet development
[notes of in-depth study paper]transbtsv2: wider instead of deep transformer for medical image segmentation
Liar report query collection network PHP source code
深拷贝真难
Solve the problem of invalid uni app configuration page and tabbar
redis6主从复制及集群
随机推荐
内网穿透工具 netapp
The real king of caching, Google guava is just a brother
Ueditor + PHP enables Alibaba cloud OSS upload
Idea remote debugging agent
Redis6 data type and operation summary
stm32逆向入门
Solve the problem of "unable to open source file" xx.h "in the custom header file on vs from the source
Ordering system based on wechat applet
Redis6 transaction and locking mechanism
Self built shooting range 2022
PostgreSQL Usage Summary (PIT)
53. 最大子数组和:给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
搭建一个仪式感点满的网站,并内网穿透发布到公网 2/2
kafaka 日志收集
::ffff:192.168.31.101 是一个什么地址?
49. 字母异位词分组:给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
Kotlin协程利用CoroutineContext实现网络请求失败后重试逻辑
【公开课预告】:视频质量评价基础与实践
MySQL get time
What is information security? What is included? What is the difference with network security?