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