Shulou(Shulou.com)06/01 Report--

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.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.