当前位置:网站首页>Leetcode-206. Reverse Linked List
Leetcode-206. Reverse Linked List
2022-07-07 07:30:00 【Eistert】
subject
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
solution
Method 1 : iteration
Suppose the linked list is 1→2→3→∅, We want to change it to ∅←1←2←3.
When traversing a linked list , Set the... Of the current node next The pointer changes to point to the previous node . Because the node does not refer to its previous node , So you have to store its previous node in advance . Before changing the reference , You also need to store the latter node . Finally, the new header reference is returned .
Code
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Complexity analysis
Time complexity :O(n), among nn It's the length of the list . You need to traverse the linked list once .
Spatial complexity :O(1).
Method 2 : recursive
Code
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
/** * To list 1->2->3->4->5 give an example * @param head * @return */
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
/* Returns the current node until the next node of the current node is empty because 5 There is no next node , So the node is returned here 5 */
return head;
}
// Recursively pass in the next node , The purpose is to reach the last node
ListNode newHead = reverseList(head.next);
/* The first round of stack ,head by 5,head.next It's empty , return 5 The second round of stack ,head by 4,head.next by 5, perform head.next.next=head That is to say 5.next=4, Point the child nodes of the child nodes of the current node to the current node At this time, the linked list is 1->2->3->4<->5, because 4 And 5 Point to each other , So disconnect here 4.next=null At this time, the linked list is 1->2->3->4<-5 Return to node 5 The third round of stack ,head by 3,head.next by 4, perform head.next.next=head That is to say 4.next=3, At this time, the linked list is 1->2->3<->4<-5, because 3 And 4 Point to each other , So disconnect here 3.next=null At this time, the linked list is 1->2->3<-4<-5 Return to node 5 The fourth round of stack ,head by 2,head.next by 3, perform head.next.next=head That is to say 3.next=2, At this time, the linked list is 1->2<->3<-4<-5, because 2 And 3 Point to each other , So disconnect here 2.next=null At this time, the linked list is 1->2<-3<-4<-5 Return to node 5 The fifth round comes out of the stack ,head by 1,head.next by 2, perform head.next.next=head That is to say 2.next=1, At this time, the linked list is 1<->2<-3<-4<-5, because 1 And 2 Point to each other , So disconnect here 1.next=null At this time, the linked list is 1<-2<-3<-4<-5 Return to node 5 Stack out complete , Final header node 5->4->3->2->1 */
head.next.next = head;
head.next = null;
return newHead;
}
}
Complexity analysis
Time complexity :O(n), among nn It's the length of the list . You need to reverse each node of the linked list .
Spatial complexity :O(n), among nn It's the length of the list . The space complexity mainly depends on the stack space of recursive calls , At most nn layer .
source
author :LeetCode-Solution
link :https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
source : Power button (LeetCode)
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
边栏推荐
- Abnova immunohistochemical service solution
- Causes and solutions of oom (memory overflow)
- Non empty verification of collection in SQL
- 普通测试年薪15w,测试开发年薪30w+,二者差距在哪?
- Select the product attribute pop-up box to pop up the animation effect from the bottom
- 组件的嵌套和拆分
- At the age of 20, I got the ByteDance offer on four sides, and I still can't believe it
- LC interview question 02.07 Linked list intersection & lc142 Circular linked list II
- Several important steps to light up the display
- 抽絲剝繭C語言(高階)指針的進階
猜你喜欢
I failed in the postgraduate entrance examination and couldn't get into the big factory. I feel like it's over
抽丝剥茧C语言(高阶)指针进阶练习
虚拟机的作用
Bindingexception exception (error reporting) processing
Academic report series (VI) - autonomous driving on the journey to full autonomy
1、 Go knowledge check and remedy + practical course notes youth training camp notes
组件的嵌套和拆分
$refs: get the element object or sub component instance in the component:
Kuboard无法发送邮件和钉钉告警问题解决
MIPS uclibc cross compile ffmpeg, support g711a encoding and decoding
随机推荐
Cloud backup project
Composition API premise
Pass child component to parent component
选择商品属性弹框从底部弹出动画效果
[Linux] process control and parent-child processes
FPGA course: application scenario of jesd204b (dry goods sharing)
Abnova immunohistochemical service solution
JS small exercise ---- time sharing reminder and greeting, form password display hidden effect, text box focus event, closing advertisement
../ And/
Flexible layout (I)
Kuboard无法发送邮件和钉钉告警问题解决
身边35岁程序员如何建立起技术护城河?
Differences between H5 architecture and native architecture
修改Jupyter Notebook文件路径
LC interview question 02.07 Linked list intersection & lc142 Circular linked list II
BGP experiment (1)
Unity C function notes
Introduction to abnova's in vitro mRNA transcription workflow and capping method
Bindingexception exception (error reporting) processing
About some details of final, I have something to say - learn about final CSDN creation clock out from the memory model