Mp.weixin.qq.com/s/6NCaKIKUs…

§ Definition of a single linked list Each node has a backward pointer (reference) to the next node, the last node points to NULL to indicate the end, and a Head pointer to the first node to indicate the beginning. The diagram below:



§ Features of single linked lists


A mouse with glasses cannot see well

We can only get the first node, how many nodes are there, what are they, where are they, and who is the last node? We don’t know any of this.

Meat bun beat a dog, there is no return

The traversal can only be done from front to back, one-way. Once you miss a node, you can only go through it again to make sure you don’t miss it this time. § Add/delete/swap nodes





Add node

There must be two Pointers, one to the node before insertion, called the prev pointer, and one to the node to be inserted, called the Node pointer. The diagram below:


The insertion process is equivalent to breaking and rebuilding a link. The diagram below:

Next = next prev.next = node





Remove nodes

In this case, it is best to have two Pointers, one pointing to the node before the node to be deleted, called the prev pointer, and one pointing to the node to be deleted, called the Node pointer. The diagram below:

Next = node.next node.next = NULL


Switching nodes

There must be two Pointers, one pointing to the node in front of the two nodes to be swapped, called prev, and one pointing to the first of the two nodes to be swapped, called first. The diagram below:

Next = first. Next first. Next = next


§ reverse


Reverse the order of the linked list. There are two ways:

Method of sequential exchange
.
Collective backward turning method

.

Method of sequential exchange

The one swaps with the two, then with the three, then with the four, then with the five, and now the one is at the end, and the two is the first one. The diagram below:


The 2 swaps with the 3, then it swaps with the 4, then it swaps with the 5, so 2 is already the second to last, and 3 is the first. The diagram below:


And so on, with 3, with 4, with 4, the reverse is done. The diagram below:

It feels a little bit like bubble sort

.


Collective backward turning method

The idea for this approach comes from physical education.

Line up and stand face to face with the PE teacher. The teacher is the head node, and the column is a single linked list.





The column turned back, and the teacher walked over to face the new column

.

The single-linked list is reoriented, the head node is reoriented

. You need three Pointers, one to the part that has been turned back, called the done pointer; A pointer to the node that is going backwards is called doing; A pointer to the remaining part to be rolled back is called a todo pointer. Done = NULL, todo = head, todo = next The diagram below:


Let the next pointer of the node that is doing point to the node that has been done; Done, doing, and todo move one node to the right. The following figure shows the operation process and the result after operation:


Next = done done = todo todo = todo. Next (if next is NULL, NULL)


Similarly, take another step, as shown in the figure below:



Similarly, the last step, when finished, completes the reverse order. The diagram below:



The comparison of the two methods, one is the direction of the linked list unchanged, change the position of the node; Second, the node position is unchanged, change the direction of the linked list. §LeetCode, K nodes in reverse order this is a problem in the LinkedList section of LeetCode. The level is hard. If k=3, reverse every 3 nodes until the end. If there are less than 3 nodes left, keep the same as before. Step 1, 0, 1, 2 reverse order



Step 2, 3, 4, 5 reverse order



Step 3: reverse 6, 7, 8



Step 4, 9 as is



Requirement: Can only define the number of constants of the extra variable (or can only use the memory of extra constants). PS: This problem is hard level, but with the above explanation, I believe that most people can solve it. Pay attention to boundary conditions and be careful.