Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points of C language single linked list example analysis, the content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

1. Remove linked list elements

Direct link to:

Remove linked list element

Title:

Train of thought:

This question needs to consider a variety of situations, the general situation is like example 1, there are multiple nodes, and the val is not contiguous, but unconventional? What about when val is continuous? When the head is val? So it needs to be classified and discussed.

General situation:

You need to define two pointers, prev and cur,cur, to the first data, and prev to the previous cur. Iterate through whether the data pointed to by cur is val. If so, point the next node of prev to the next node of cur, and cur=cur- > next,prev follow cur until cur walks to NULL.

Continuous val:

When we take a closer look, it is not difficult to find that continuous val can be solved under normal circumstances, but the head val is not.

Head val:

At this time, in addition to the two pointers prev and cur just defined, there is also a head pointing to the header. When the header is val, point cur to the next location, and head moves together until head is assigned to prev when the data pointed to by cur is not val. At this time, the rest can be dealt with as usual.

The code is as follows:

Struct ListNode* removeElements (struct ListNode* head, int val) {struct ListNode*cur=head; struct ListNode*prev=NULL; while (cur) {if (cur- > validated Val) {prev=cur; cur=cur- > next;} else {struct ListNode*next=cur- > next; if (prev==NULL) {free (cur) Cur=next; head=next;} else {prev- > next=cur- > next; free (cur); cur=prev- > next;} return head;} 2, reverse the linked list

Direct link to:

Reverse linked list

Title:

Train of thought:

Method 1: three pointers flip direction

Define three pointers, N1, N2, n3, to point to NULL, the first data, and the second data. Let the next of N2 point to N1, assign N2 to N1, then assign N2 to N2, then perform the operation of n3 to n3-> next, and then repeat until N2 points to empty. Note, however, that you should first determine whether the linked list is NULL, and if so, return NULL. In addition, make sure that you don't move when n3 is empty, and just assign N2 to N2.

The code is as follows:

Struct ListNode* reverseList (struct ListNode* head) {if (head==NULL) {return NULL;} struct ListNode*n1=NULL; struct ListNode*n2=head; struct ListNode*n3=n2- > next; while (N2) {N2-> next=n1; N1: N2; N2: n3; if (n3) {n3: n3-> next;}} return N1;}

Method 2: head insertion

This method needs to create another linked list, create a new header newhead pointing to NULL, define a pointer cur to the first data in the original linked list, and note that you have to define a pointer next to point to the next node of cur. Traverse the original linked list, take the node off and insert the head into the linked list where the newhead is located. Each update newhead is assigned to cur, as shown in the figure:

The code is as follows:

Struct ListNode* reverseList (struct ListNode* head) {if (head==NULL) {return NULL;} struct ListNode*cur=head; struct ListNode*next=cur- > next; struct ListNode*newhead=NULL; while (cur) {cur- > next=newhead; newhead=cur; cur=next; if (next) {next=next- > next;}} return newhead;} 3, intermediate node of the linked list

Direct link to:

The middle node of the linked list

Title:

Train of thought:

Fast and slow pointer

In this question, we should pay attention to the odd and even numbers. if it is an odd number, such as example 1, then the intermediate node value is 3, while the even number, such as example 2, returns the second intermediate node. In this question, we define where two pointers, slow and fast, point to the first data. The difference is that slow takes one step at a time and fast takes two steps at a time. When fast reaches the tail pointer, slow is the intermediate node

The code is as follows:

Struct ListNode* middleNode (struct ListNode* head) {struct ListNode*slow=head; struct ListNode*fast=head; while (fast&&fast- > next) {slow=slow- > next; fast=fast- > next- > next;} return slow;} 4, the last node in the linked list

Direct link to:

The last but one node in the linked list

Title:

Train of thought:

Fast and slow pointer

Define two pointers slow and fast, let fast take k steps first, and then let slow and fast go at the same time. When fast reaches the tail, slow is the last k, because in this case, the gap between slow and fast is always k, and ends when fast goes empty. This question can also take the KMel 1 step, but it ends when the fast comes to the end, that is, when the next node of the fast points to the space, it is all the same. Take away step k as an example, as shown in the figure:

The code is as follows:

Struct ListNode* FindKthToTail (struct ListNode* pListHead, int k) {/ / write code here struct ListNode*fast=pListHead; struct ListNode*slow=pListHead; while (k color -) {/ / if judgment to prevent k from being greater than the length of the linked list if (fast==NULL) return NULL; fast=fast- > next;} while (fast) {fast=fast- > next; slow=slow- > next;} return slow 5. Merge two ordered linked lists

Direct link to:

Merge two ordered linked lists

Title:

Train of thought:

Method 1: merge (take the small tail insert)-lead node

Suppose the header of the new linked list is called head and points to NULL, and you also need to define a pointer tail to facilitate subsequent tail-finding, compare the values of list1 and list2 nodes in turn, put the small ones on the new linked list head, and update tail, and then update list1 or list2. When one of the list1 and list2 linked lists is empty, just copy all the remaining elements of the remaining linked list into it.

The code is as follows:

Struct ListNode* mergeTwoLists (struct ListNode* list1, struct ListNode* list2) {/ / check if list1 or list2 is NULL from the beginning if (list1==NULL) {return list2;} if (list2==NULL) {return list1;} struct ListNode*head=NULL; struct ListNode*tail=head While (list1&&list2) {if (list1- > valval) {if (tail==NULL) {head=tail=list1;} else {tail- > next=list1; tail=list1;} list1=list1- > next } else {if (tail==NULL) {head=tail=list2;} else {tail- > next=list2; tail=list2;} list2=list2- > next }} / / when one of list1 and list2 goes empty if (list1==NULL) {tail- > next=list2;} else {tail- > next=list1;} return head;}

Method 2: the head node of the sentry position

Explain the lead node:

For example, the same chain table stores 1pm 2pm 3. There are only three nodes without a leader, and head points to 1. The lead node also stores three values, but there are four nodes. Head points to the header node, which does not store valid data.

The lead node has the following advantages: it is not necessary to judge whether head and tail are empty, nor does it have to judge whether list1 and list2 are empty. As with the above idea, take the small ones and insert them at the end, and then link them directly to the back of the tail. But be careful to return the next of head, because the linked list given by the title does not lead, and head itself points to that header, so return to the next one.

The code is as follows:

Struct ListNode* mergeTwoLists (struct ListNode* list1, struct ListNode* list2) {struct ListNode* head = NULL, * tail = NULL; head = tail = (struct ListNode*) malloc (sizeof (struct ListNode)); head- > next = NULL; while (list1 & & list2) {if (list1- > val)

Val) {tail- > next = list1; tail = list1; list1 = list1- > next;} else {tail- > next = list2; tail = list2; list2 = list2- > next }} / / when one of list1 and list2 goes empty if (list1 = = NULL) {tail- > next = list2;} else {tail- > next = list1;} struct ListNode* list = head- > next; free (head); head = NULL return list;} 6, linked list splitting

Direct link to:

Linked list segmentation

Title:

Train of thought:

Define two linked lists lesshead and greaterhead. Traverse the original linked list and set the

Insert x into list 2, and finally link list 1 with list 2. Define two tail pointers to follow the new elements in list 1 and 2

The code is as follows:

Class Partition {public: ListNode* partition (ListNode* pHead, int x) {/ / write code here struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail; lessHead = lessTail = (struct ListNode*) malloc (sizeof (struct ListNode)); greaterHead = greaterTail = (struct ListNode*) malloc (sizeof (struct ListNode)); lessTail- > next = greaterTail- > next = NULL; struct ListNode* cur = pHead While (cur) {if (cur- > val)

Next = cur; lessTail = lessTail- > next;} else {greaterTail- > next = cur; greaterTail = greaterTail- > next;} cur = cur- > next;} / / merge lessTail- > next = greaterHead- > next; greaterTail- > next = NULL Struct ListNode* list = lessHead- > next; free (lessHead); free (greaterHead); return list;}}; these are all the contents of the article "C language single linked list example Analysis". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.