I Flip single linked list

1. Three pointer method

When we use three pointers to flip a single linked list, we need to consider three situations:
(1) When the linked list is empty or there is only one, there is no need to turn it over and return directly
(2) This is the normal situation shown in the figure. When all three pointers point to a value.
(3) When the pointer to the last node is null, the pointer will jump out of the loop.
Illustration:

The code and notes are as follows:

ListNode ReverseList(ListNode head)
{
	if(head==NULL|| head.next=NULL)//If it is empty, or there is only one node. There is no need to reverse
	{
		return head;
	}
	//Here are two or more nodes
	ListNode left=head;
	ListNode mid=left.next;
	ListNode right=mid.next;//Pointing to the third node may be empty
	while(right)
	{
		mid.next=left;//Change the direction of two nodes
		//The remaining cornerstone moves the three pointers backward
		left=mid;
		mid=right;
		right = right.next;
	}
	//The third node is empty, leaving only two nodes
	mid.next=left;
	//The original head node pointer has not changed, so it needs special treatment. Let it point to null as the tail of the new linked list.
	head.next=null;
	
	head=mid;
	return head;
}

2. Head insertion method (recommended)

The bit plane of the three pointer method is a little cumbersome. At this time, it is very simple to insert the head of each node of the original linked list into a new linked list.

The code is as follows;

ListNode ReverseList(ListNode head)
{
	if(head==NULL||head.next==NULL)
	{
		return head;
	}
	ListNode new_head=NULL;
	while(head)
	{
		//First take down the original chain header node
		ListNode p=head;
		//The original linked list pointer moves back
		head=head.next;
		//Insert into the head of a new linked list
		p.next=new_head;
		new_head=p;
	}
	return new_head;
}

II Two monotonically increasing single linked lists are merged into a non decreasing single linked list

1. Normal practice

(1) Two linked lists, select the node with smaller value.
(2) Move the original pointer of this node back to the next node
(3) Insert the node into the new node.
Special judgment: when a new node is inserted for the first time?
(4) When a linked list reaches the end, you only need to connect another linked list to the back of the new linked list. So, how to judge which linked list ends first?

The code and corresponding comments are as follows for your understanding:

ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
	//If one of them is empty, just return the other directly
	if(pHead1==NULL) return pHead2;
	if(pHead2==NULL) return pHead1;
	
	//First declare the head and tail pointers of the two nodes of the new linked list
	ListNode* head=NULL;//Easy to return
	ListNode* end=NULL;//Easy tail insertion
	//When both linked lists are not empty
	while(pHead1 && pHead2)
	{
		//1. Call out the node to delete, which is the smaller value
		ListNode* p=pHead1->val > pHead2->val ? pHead2 : pHead1;
		//2. Delete target node
		if(p==pHead1)
			pHead1=pHead1->next;
		else
			pHead2=pHead2->next;
		//3. Insert the node into the new linked list
		
		if(head==NULL)//If this is the first insertion
		{
			head=p;
			end=p;
		}
		else
		{
			//If it's not the first time to insert, just insert the tail directly
			end->next=p;
			end=end->next;
		}
	}
	//Jumping out of the loop means that one of them is empty or both are empty
	if(pHead1==NULl)
		end->next=pHead2;
	else
		end->next=pHead1;
	
	return head;
}

2. Recursive implementation

ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
	if(pHead1==NULL) return pHead2;
	if(pHead2==NULL) return pHead1;
	
	ListNode* head=nullptr;
	//Find the appropriate node, that is, the smaller value. In this call, connect it to the back of the new linked list
	if(pHead1->val > pHead2->val)
	{
		head=pHead2;
		pHead2=pHead2.next;
	}
	else
	{
		head=pHead1;
		pHead1=pHead1.next;
	}
	//Recursively realize the connection of the next node
	head->next = Merge(pHead1 , pHead2);
	return head;
}

III Binary tree determines whether b is a subtree of a (empty tree is not a subtree of any tree)

First of all, we need to know that a binary tree itself is implemented recursively. Naturally, when judging whether it is a subtree, we need to start from the root node, recursively call the function to judge its left subtree, and recursively call the function to judge whether the right subtree is a subtree.

The code and notes are as follows:

bool IsSame(TreeNode* root1,TreeNode* root2)//Compare whether the left and right subtrees are equal
{
	if(root2==NULL)
	{
		return true;
	}
	if(root1==NULL)
	{
		return false;
	}
	if(root1->val!=root2->val)
		return false;
	//Recursively judge whether subtrees are equal
	return IsSame(root1->left,root2->left)&&IsSame(root1->right,root2->val);
}

bool HasSubtree(TreeNode* root1,TreeNode* root2)
{
	if(root1==NULL || root2==NULL) return false;
	//Set a flag
	bool result=false;
	//Find the starting position first
	if(root1->val== root2->val)
	{
		result=IsSame(root1,root2);
	}
	//In the past, there are two cases, either the values of the two starting positions are not equal, or the subtrees do not match
	//When the equal conditions are met, continue to judge in the next step
	if(result!=true)
	{
		result=HasSubtree(root1->left,root2);
	}
	if(result!=true)
	{
		result=HasSubtree(root1->right,root2);
	}
}

Note: for recursive calls, you may have problems that you don't quite understand. You can draw your own function recursion diagram for further understanding. If you don't quite understand, you can leave a message and I will try my best to answer it.

IV Here comes the little incentive

In our daily life and study, there is always a "three minute heat" for something. At a certain moment of persistence, we will doubt what we are doing now and whether it is necessary to persist,
We just think too much and do very little.
When you have a clear goal and devote yourself to it, you won't have so many messy ideas in your mind. So,
Move on! hxd.