当前位置:网站首页>2022.02.13 - NC001. Reverse linked list
2022.02.13 - NC001. Reverse linked list
2022-07-06 08:21:00 【A CAI continues to work hard】
List of articles
1. subject
2. Ideas
(1) Utilization stack ( Overtime )
- First use the stack push() Press the nodes into the stack in turn , Reuse stack pop() Pop up the nodes in turn , Reversal can be achieved , But it will time out .
(2) Discussion by situation
- Discuss separately 0 Nodes 、1 Nodes 、2 Nodes 、3 More than nodes :0 Nodes 、1 Nodes return directly head that will do ;2 Just reverse the nodes directly ;3 More than nodes need to use two variables to point to head Of next and next Of next,head Used to point to the node pointed to in the reverse operation ,next Used to point to the node pointed to in the reverse operation , That is, the head node of the new linked list ,nextNext Used to point to the head node of the original linked list .
(3) Optimize
- And (2) The idea is basically the same , But more concise .
- Variable last Point to the node pointed to in the reverse operation , Variable cur Point to the node pointed to in the reverse operation , That is, the head node of the new linked list , Variable next Point to the head node of the original linked list .
- Because the order in the loop body is moving variables next -> Reverse operation -> Moving variables last -> Moving variables cur, So finally, variables last Point to the head node of the new list .
3. Code
import java.util.Stack;
public class Test {
public static void main(String[] args) {
ListNode listNode1 = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
listNode1.next = listNode2;
listNode2.next = listNode3;
Solution2 solution = new Solution2();
ListNode listNode = solution.ReverseList(listNode1);
System.out.println(listNode.val);
System.out.println(listNode.next.val);
System.out.println(listNode.next.next.val);
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
class Solution {
public ListNode ReverseList(ListNode head) {
Stack<ListNode> stack = new Stack<>();
while (head != null) {
stack.push(head);
head = head.next;
}
head = stack.pop();
ListNode listNode = head;
while (!stack.isEmpty()) {
listNode.next = stack.pop();
listNode = listNode.next;
}
return head;
}
}
class Solution1 {
public ListNode ReverseList(ListNode head) {
if (head != null) {
// At least two points
if (head.next != null) {
// At least three points
if (head.next.next != null) {
ListNode next = head.next;
ListNode nextNext = next.next;
head.next = null;
while (nextNext != null) {
next.next = head;
head = next;
next = nextNext;
nextNext = next.next;
}
next.next = head;
head = next;
}
// There are only two points
else {
head.next.next = head;
head = head.next;
head.next.next = null;
}
}
}
return head;
}
}
class Solution2 {
public ListNode ReverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode last = null;
ListNode cur = head;
ListNode next = null;
while (cur != null) {
next = cur.next;
cur.next = last;
last = cur;
cur = next;
}
return last;
}
}
边栏推荐
- 【MySQL】日志
- Analysis of pointer and array written test questions
- 08- [istio] istio gateway, virtual service and the relationship between them
- 1. Color inversion, logarithmic transformation, gamma transformation source code - miniopencv from zero
- Summary of MySQL index failure scenarios
- 使用 TiDB Lightning 恢复 S3 兼容存储上的备份数据
- Easy to use tcp-udp_ Debug tool download and use
- [research materials] 2021 Research Report on China's smart medical industry - Download attached
- [2022 广东省赛M] 拉格朗日插值 (多元函数极值 分治NTT)
- Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
猜你喜欢
"Designer universe" APEC design +: the list of winners of the Paris Design Award in France was recently announced. The winners of "Changsha world center Damei mansion" were awarded by the national eco
C language - bit segment
A Closer Look at How Fine-tuning Changes BERT
[t31zl intelligent video application processor data]
你想知道的ArrayList知识都在这
Online yaml to CSV tool
The resources of underground pipe holes are tight, and the air blowing micro cable is not fragrant?
A Closer Look at How Fine-tuning Changes BERT
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Database basic commands
随机推荐
[research materials] 2022 China yuancosmos white paper - Download attached
National economic information center "APEC industry +": economic data released at the night of the Spring Festival | observation of stable strategy industry fund
使用 Dumpling 备份 TiDB 集群数据到兼容 S3 的存储
The State Economic Information Center "APEC industry +" Western Silicon Valley will invest 2trillion yuan in Chengdu Chongqing economic circle, which will surpass the observation of Shanghai | stable
1. Color inversion, logarithmic transformation, gamma transformation source code - miniopencv from zero
CISP-PTE实操练习讲解
Use Alibaba icon in uniapp
在 uniapp 中使用阿里图标
使用 TiUP 升级 TiDB
LDAP Application Section (4) Jenkins Access
LDAP應用篇(4)Jenkins接入
Permutation and combination function
2022 Inner Mongolia latest construction tower crane (construction special operation) simulation examination question bank and answers
LDAP application (4) Jenkins access
sys.argv
化不掉的钟薛高,逃不出网红产品的生命周期
升级 TiDB Operator
Sanzi chess (C language)
String to leading 0
2022 Inner Mongolia latest water conservancy and hydropower construction safety officer simulation examination questions and answers