This is the 31st day of my participation in the August Text Challenge.More challenges in August
Research algorithm will
5. Insert operation of double linked list
We now want to implement the storage element e, node S insert into nodes P and p->next, as shown in the figure
s->prior = p; / / as shown in figure 1)
s->next = p->next; / / as shown in figure 2)
p->next->prior = s; / / as shown in figure 3
p->next = s; / / as shown in figure 4
Copy the code
The key of the insert steps lies in the order in which they are inserted. Assuming that step 4 is executed first, p->next is changed to S in advance. Since p->next is used between step 2 and step 3, the final insert fails.
6. Delete the double-linked list
If you understand the insert operation, then the delete operation is relatively easy. Take the double-linked list as an example, as shown in the following flowchart for deleting node P, the following steps are required to delete node P:
p->prior->next = p->next; / / as shown in figure 1)
p->next->prior = p->prior; / / as shown in figure 2)
free(p) // Free up space
Copy the code
7. The inverse
Method one: head insertion method
The head pointer traverses the linked list and moves forward continuously. P is used to record a node before head. Next is modified to point to P and a temp pointer is used to point (save) the next node of head.
ListNode* reverseList(ListNode* head){
ListNode *tem,*p = NULL;
while(head ! =NULL){
tem = head->next; // Black arrow
head->next = p; // Blue curved arrow
p = head; / / move
head = tem; / / move
}
return p;
}
Copy the code
Method two: recursion
The difference between recursion and iteration is that recursion is processed from the end of the list, traversing the list, recording the end node, recording with newhead, as the head node of the new list, and assigning head to head->next-> Next when the working pointer recursively returns, And set head->next to NULL.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x),next(NULL) {}};class Solution {
public:
ListNode* reverseList(ListNode* head){
if ( head == NULL||head->next == NULL)
return head;
ListNode* newhead = reverseList ( head ->next ) ; // recurse to the end of the chain
head->next->next = head; // Reverse the ripple table
head->next = NULL; // Set the pointer to NULL
return newhead; // Newhead always points to the head of the new list}};Copy the code