# 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
{
}
//Here are two or more nodes
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.

}
```

## 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)
{
{
}
{
//First take down the original chain header node
//The original linked list pointer moves back
}
}
```

# 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?

```ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
//If one of them is empty, just return the other directly

//First declare the head and tail pointers of the two nodes of the new linked list
ListNode* end=NULL;//Easy tail insertion
//When both linked lists are not empty
{
//1. Call out the node to delete, which is the smaller value
//2. Delete target node
else
//3. Insert the node into the new linked list

if(head==NULL)//If this is the first insertion
{
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
else

}
```

## 2. Recursive implementation

```ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{

//Find the appropriate node, that is, the smaller value. In this call, connect it to the back of the new linked list
{
}
else
{
}
//Recursively realize the connection of the next node
}
```

# 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.

Tags: Java C++

Posted by phpdoodler on Mon, 18 Apr 2022 15:03:55 +0930