1. Merge two ordered linked lists
1.1 Title Description
This topic comes from leetcode 21. Merging two ordered linked lists
Tips:
1.2 interface function
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
}
1.3 general framework
1.3.1 train of thought analysis
- Create a new linked list, that is, create a header node
Here we need to have two pointers, each pointing to null
- Why do you want a head because you want to return the head pointer
- Why a tail? It's convenient for tail insertion
- Then the array is compared up and down, and the small ones are placed in the new linked list in turn
The comparison uses an L1 and an L2 pointer to point to the head nodes of the original two linked lists respectively
- l1 points to the next pointer, and then the head of the new linked list does not move. The tail pointer points to this node, which means tail pointer
- Loop continuously. Finally, when the L1 or L2 pointer of one of the linked lists points to NULL, the loop stops
- Finally, connect the remaining linked list behind the new linked list
1.3.2 specific steps
First, prevent incoming and the pointer is empty
//Note that any null pointer will collapse at the first time
//If it is empty, just return another one directly
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l2;
}
Here, you'd better not put the header in the while loop. Just solve it before the loop
if(l1->val<l2->val)
{
head=tail=l1;
l1=l1->next;
}
else
{
head=tail=l2;
l2=l2->next;
}
The while loop keeps going until it finally comes to NULL by a pointer
while(l1&&l2)
{
//Take the small tail and insert it into the new linked list
if(l1->val<l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
//tail goes to a new position
tail=tail->next;
}
When one is null, connect the other to the new linked list, and then return the header pointer
//l2 is empty
if(l1)
{
tail->next=l1;
}
//l1 is empty
if(l2)
{
tail->next=l2;
}
return head;
1.4 specific implementation
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
//Note that any null pointer will collapse at the first time
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct ListNode* head=NULL;
struct ListNode* tail=NULL;
//Don't put it in the loop for the first time
if(l1->val<l2->val)
{
head=tail=l1;
l1=l1->next;
}
else
{
head=tail=l2;
l2=l2->next;
}
while(l1&&l2)
{
//Take the small tail and insert it into the new linked list
if(l1->val<l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
//tail goes to a new position
tail=tail->next;
}
//l2 is empty
if(l1)
{
tail->next=l1;
}
//l1 is empty
if(l2)
{
tail->next=l2;
}
return head;
}
1.5 method selection
Another leading node method:
-
Set a sentinel position head node
-
Follow the same judgment steps for tail interpolation
Don't forget here = = tail - > next = null== Avoid both being empty
-
The remaining steps are the same, mainly less judgment steps
-
Note that the node before release is processed finally
//Create a sentinel position head node
struct ListNode* head=NULL;
struct ListNode* tail=NULL;
head =tail=(struct ListNode*)malloc(sizeof(struct ListNode));
tail->next=NULL;//Prevent both from being empty to facilitate tail insertion
while(l1&&l2)
{
//Take the small tail and insert it into the new linked list
if(l1->val<l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
tail=tail->next;
}
//l2 is empty
if(l1)
{
tail->next=l1;
}
//l1 is empty
if(l2)
{
tail->next=l2;
}
struct ListNode* node=head;
head=head->next;
free(node);
return head;
2. Split linked list
2.1 Title Description
This is the first problem with medium difficulty
This topic comes from leetcode split linked list
Tips:
2.2 interface function
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x){
}
2.3 general framework
If you give such an example, although the original question does not require that the order remains unchanged, here you can try it with the requirements of niuke.com
At this time, our answer should be that the relative order cannot be changed, so the final output is like this
2.3.1 train of thought analysis
Insert the tail less than x into a linked list, then insert the tail greater than x into a linked list, and finally connect the two linked lists
- Create the head nodes of two sentinel positions and create corresponding head and tail pointers respectively
- Respectively judge that if the value of the node is less than the given x, it will be inserted into the decimal linked list, otherwise the large linked list
- Of course, the tail pointer should automatically keep up and become the tail. After walking, you will find that the approximate order has not changed
- Finally, it's ok to link together. The termination condition is that the original linked list is completed
2.3.2 specific steps
Follow the first idea step by step
There is a problem, prompt
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next=NULL;
greaterTail->next=NULL;
struct ListNode*cur=head;
while(cur)
{
if(cur->val<x)//Only those with < are processed
{
lessTail->next=cur;
lessTail=lessTail->next;
}
else
{
greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
//Connect two linked lists
lessTail->next=greaterHead->next;
head=lessHead->next;
free(lessHead);
free(greaterHead);
return head;
}
This shows that there is a problem and it needs to be improved
Generally, the cause of time overrun is dead cycle
Sometimes the memory overrun is caused by other reasons. This problem is not because it exceeds the memory complexity. We should think about the extreme situation
This situation is hard to think of and needs a lot of experience
We set the next pointer of greater to null because the current node reuses the nodes of the original linked list, and its next pointer may point to a node less than x, which will form a ring. We need to cut off this reference.
It is because of the dead cycle that an error is reported
The solution is to empty the last node
//crux greaterTail->next=NULL;
2.4 specific implementation
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next=NULL;
greaterTail->next=NULL;
struct ListNode*cur=head;
while(cur)
{
if(cur->val<x)//Only those with < are processed
{
lessTail->next=cur;
lessTail=lessTail->next;
}
else
{
greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
//Connect two linked lists
lessTail->next=greaterHead->next;
//crux
greaterTail->next=NULL;
head=lessHead->next;
free(lessHead);
free(greaterHead);
return head;
}
Summary:
In fact, there are many solutions to this problem. If you are interested, you can have a look at the solutions to multiple problems
That's all for this topic. If you feel you have something to gain, please click three times. Thank you