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

This article introduces the relevant knowledge of "how to reverse a single linked list by Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

How to reverse a single linked list?

Method 1: save the single linked list as an array and reverse it according to the index of the array.

Method 2: use three pointers to traverse the single linked list and reverse it one by one.

Method 3: from the second node to the Nth node, insert node by node into the first node (head node), and finally move the first node to the end of the new table.

Method 4: recursion (I believe what we are all familiar with is that most of the problems in the tree can be solved by recursion. But what we are not familiar with is that recursion can also be used for some problems with single linked lists. It can be considered that a single linked list is always a tree with only left (right) subtrees, so we can consider using recursion to solve the problem. In other words, because the structure of the single linked list itself has self-similar characteristics, it can be solved by recursion.

Method 1:

Waste of space.

Method 2:

Use p and Q pointers to work together to reverse the pointing between the two nodes, while recording the rest of the linked list with r.

P = head

Q = head- > next

Head- > next = NULL

P = Q

Q = r

Q-> next = p

Q = r

The third cycle.

The specific code is as follows

ActList* ReverseList2 (ActList* head) {/ / ActList* temp=new ActList; if (NULL==head | | NULL==head- > next) return head; / / there is no need to reverse with less than two nodes. ActList* p; ActList* Q; ActList* r; p = head; Q = head- > next; head- > next = NULL; / / the old header pointer is the new tail pointer, and next needs to point to NULL while (Q) {r = Q-> next; / / first keep the next step pointer Q-> next = p; / / then p Q work alternately and reverse p = Q Q = r;} head=p; / / finally Q must point to NULL, so p is returned as the new header pointer return head;}

If you find the above loop-forming and then-breaking process difficult to understand, you can consider the following approach, adding an intermediate variable and using three variables to achieve.

Struct ListNode {int val; ListNode* next; ListNode (int a): val (a), next (NULL) {}}; ListNode* reverseLinkedList3 (ListNode* head) {if (head==NULL | | head- > next==NULL) return head; ListNode* paired headers; / / points to head ListNode* ringing headers-> next; / / points to the nodes to be transported, that is, all nodes ListNode* m=NULL from the second node to the last node in turn / / Node ListNode* tail=head- > next; while (rushing null) {/ / bug2 loop statement is misspelled and while is written as if missur; rsqur-> next; m-> next=p- > next; p-> next=m / / if (ringing null) / / std::coutC- > D has been reversed and has become D-> C-> B, so the next thing to do is to take D-> C-> B as a whole and let the overall next point to A, so the problem turns into a reversal of B-> C-> D. that,

You can assume that C-> D has reversed and become D-> C, then the next thing to do is to look at D-> C as a whole and let the overall next point to B, so the problem turns into a reversal of C-> D. that,

You can assume that D (actually D-> NULL) has been reversed and has become D (actually head- > D), then the next thing to do is to take D (actually head- > D) as a whole and let the next of the whole point to C, so the problem turns into inverted D.

The above process is a recursive process, and the most troublesome question is, what about keeping the head pointer of the new linked list? I thought of two ways.

In the first implementation of the recursive version, the header pointer of the new linked list is represented by the member variable m_phead of the class.

Struct ListNode {int val; ListNode* next; ListNode (int a): val (a), next (NULL) {}}; class Solution {ListNode* reverseLinkedList4 (ListNode* head) {/ / input: the header pointer if (head==NULL) return NULL; if (head- > next==NULL) of the old linked list; return head;} ListNode* new_tail=reverseLinkedList4 (head- > next) New_tail- > next=head; head- > next=NULL; return head; / / output: tail pointer of the new linked list} ListNode* variable defined for reverseLinkedList4 (ListNode* head)}

The second way is to add a reference parameter new_head, which is used to hold the header pointer of the new linked list.

Struct ListNode {int val; ListNode* next; ListNode (int a): val (a), next (NULL) {}}; class Solution {ListNode* reverseLinkedList5 (ListNode* head, ListNode* & new_head) {/ / input parameter head is the header pointer of the old linked list. New_head is the header pointer to the new linked list. If (head==NULL) return NULL; if (head- > next==NULL) {new_head=head; / / assigns a value to new_head when the tail pointer of the old linked list, that is, the head pointer of the new linked list, is processed. Because it is a referential parameter, the value of new_head is passed layer by layer in the next call. Return head;} ListNode* new_tail=reverseLinkedList5 (head- > next,new_head); new_tail- > next=head; head- > next=NULL; return head; / / the output parameter head is the tail pointer of the new linked list. This is the content of "how to reverse a single linked list by Java". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.