How to analyze Reverse Linked List
How to analyze Reverse Linked List, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.
Reverse Linked List
Title
Reverses a single linked list.
Example:
Enter: 1-> 2-> 3-> 4-> 5-> NULL
Output: 5-> 4-> 3-> 2-> 1-> NULL
Advanced:
You can iterate or recursively reverse the linked list. Can you solve the problem in two ways?
Problem-solving ideas
Set up three nodes: pre, cur, next
(1) check whether the cur node is NULL each time. If so, end the loop and get the result.
(2) if the cur node is not NULL, set the temporary variable next to the next node of cur first.
(3) change the next node of cur to point to pre, and then pre move cur,cur to next.
(4) repeat (1) (2) (3)
Animation demonstration
The animation GIF is a little big. Please wait a little while to load and display ^ _ ^.
Animation demonstration reference code 1. Iterative approach to deal with 2. The recursive way to deal with 1 stroke / 206. Reverse Linked List
2max / https://leetcode.com/problems/reverse-linked-list/description/
3//
4Universe / recursive way to reverse the linked list
5max / time complexity: O (n)
6max / space complexity: O (1)
7class Solution {
8public:
9 ListNode* reverseList (ListNode* head) {
ten
11 / / Recursive termination condition
12 if (head = = NULL | | head- > next = = NULL)
13 return head
fourteen
15 ListNode* rhead = reverseList (head- > next)
sixteen
17 / / head- > next now points to the tail node of the linked list after head
18 / / head- > next- > next = head put the head node at the tail
19 head- > next- > next = head
20 head- > next = NULL
twenty-one
22 return rhead
23}
24}
Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.
