1. Description of the problem

English description

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Product description

Given the head node of a single linked list, reverse the list and return the reversed list.

Example 1:

​

Example 2:

​

Example 3:

Input: head = [] Output: []

Tip:

The number of nodes in the linked list ranges from [0, 5000] -5000 <= node. val <= 5000

Advanced: Lists can be reversed iteratively or recursively. Can you solve the problem in two ways?

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Second, the idea of solving the problem

1. Head insertion method

Without further ado, let’s do the figure above

​

In simple terms, the nodes of the original linked list are continuously inserted between the virtual head node head and the next node after the head node.

2. Tail insertion method

Similar to the headplug method, but instead of creating a head node, create an empty node (tail node);

Then continuously link the nodes of the original list to the head of the new list.

​

3, the recursion

There are two main elements of recursion: exit, how to recurse.

Export conditions

When the list passed is empty or has only one node, because there is no need to reverse the list.

How the recursion

The core idea of recursion is to divide a linked list into two parts: the head node and the other nodes.

The other nodes can continue to call recursive functions as a new linked list. That is, when we put the list of other nodes into the function, we can treat it as if it has been reversed.

​

Assuming that the other nodes have been reversed, the next thing to consider is rejoining the head node to the end of another part of the list

​

To do this, we need two pointer variables: tail (pointing to the tail node of the reversed part, which is 2 in the figure above) and h (pointing to the head node of the reversed list, which is 5 in the figure above). Tail =head->next, h=reverseList(head->next).

​

The next step is to connect the head node to the tail node and return the new head node H

class Solution { public: ListNode * reverseList (ListNode * head) {/ / when the list is empty or when there is only one node Don't need to reverse the if (head = = nullptr | | head - > next = = nullptr) return head; // The core idea of recursion is to break a linked list into two parts: ListNode *tail = head->next; ListNode *tail = head->next; *h = reverseList(head->next); head->next = tail->next; tail->next = head; return h; }};Copy the code

Three, AC code

C++

The first interpolation

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *h = new ListNode; If (head == nullptr) return head; ListNode *p = head, *q = head->next; while(p ! = nullptr) { p->next = h->next; h->next = p; p = q; if(q ! = nullptr) q = q->next; } return h->next; }};Copy the code

The tail interpolation

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *newList = nullptr; If (head == nullptr) return head; ListNode *p = head, *q = head->next; while(p ! = nullptr) { p->next = newList; newList = p; p = q; if(q ! = nullptr) q = q->next; } return newList; }};Copy the code

recursive

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * reverseList (ListNode * head) {/ / when the list is empty or when there is only one node Don't need to reverse the if (head = = nullptr | | head - > next = = nullptr) return head; // The core idea of recursion is to break a linked list into two parts: ListNode *tail = head->next; ListNode *tail = head->next; *h = reverseList(head->next); head->next = tail->next; tail->next = head; return h; }};Copy the code

Java

recursive

/** * 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 { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode tail = head.next, h = reverseList(head.next); head.next = tail.next; tail.next = head; return h; }}Copy the code

Fourth, the problem solving process

The first,

Head plug. I’m glad I didn’t lose that old data structure teacher thing.

​

The second stroke

In situ reverse

​

The third stroke

Recursion, this is also a new solution, compared to other algorithms can obviously see that recursion is more memory consumption

​

​