Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "what are the common algorithms of linked lists". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The linked list node is declared as follows:

Struct LinkList {int value; LinkList * next;}

The following is the operation of a single linked list without leading nodes.

1. Establish a single linked list according to input

Insert the input node into the header of the linked list.

/ / create a single linked list based on input: insert LinkList * BuildList () {LinkList * head = NULL; int data; int i = 0 in the header of the linked list; while (scanf ("% d", & data)! = EOF) {/ / scanf ("% d", & data); + + I; LinkList * new_node = (LinkList *) malloc (sizeof (LinkList)) If (NULL = = new_node) {fprintf (stderr, "malloc failed"); return head;} new_node- > value = data; if (head = = NULL) {new_node- > next = NULL Head = new_node;} else {new_node- > next = head; head = new_node;}} return head;} 2. Linked list insert operation

When inserting a linked list, pay attention to the situation when the linked list is empty.

(1) insert node LinkList * InsertToHead (int value, LinkList * head) {LinkList * new_node = (LinkList *) malloc (sizeof (LinkList)) in the chain header; if (new_node = = NULL) {fprintf (stderr, "malloc failed"); return head;} new_node- > value = value; new_node- > next = NULL If (head = = NULL) {head = new_node;} else {new_node- > next = head; head = new_node;} return head } (2) insert the node LinkList * InsertToTail (int value, LinkList * head) {LinkList * new_node = (LinkList *) malloc (sizeof (LinkList)); if (new_node = = NULL) {fprintf (stderr, "malloc failed") at the end of the linked list; return head;} new_node- > value = value; new_node- > next = NULL If (head = NULL) head = new_node; else {LinkList * pnode = head; while (pnode- > next! = NULL) pnode = pnode- > next; pnode- > next = new_node;} return head;} 3. Delete operation of linked list

Note the deletion when the linked list has only one node.

/ / Delete a node LinkList* DeletebyValue (int value, LinkList* head) {if (head = = NULL) return head; LinkList* pToDelete = NULL; if (head- > value = = value) {pToDelete = head; head = head- > next;} else {LinkList* p = head While (p-> next! = NULL & & p-> next- > value! = value) p = p-> next; if (p-> next! = NULL) {pToDelete = p-> next; p-> next = pToDelete- > next } if (pToDelete! = NULL) {free (pToDelete); pToDelete = NULL;} return head;} 4. Find the number of nodes in a single linked list

Check to see if the linked list is empty. The time complexity is O (n). This operation does not need to check whether the linked list is empty, as shown in the following code. If the linked list is empty, it will return 0 empty *. **

Unsigned int Length (LinkList * head) {unsigned int length = 0; LinkList * p = head; while (p) {+ + length; p = p-> next;} return length;} 5. Print linked list element (1) forward print linked list / / print single linked list void PrintList (LinkList * head) {LinkList * p = head; while (p) {printf ("% d", p-> value); p = p-> next;} printf ("\ n") } (2) print linked list in reverse order / / print single linked list in reverse order: non-recursive void RPrintList (LinkList* head) {if (NULL = = head) return; stack list_stack; while (head) {list_stack.push (head- > value); head = head- > next } while (! list_stack.empty ()) {printf ("% d", list_stack.top ()); list_stack.pop ();} printf ("\ n");} / / print single linked list in reverse order: recursive void RPrintListRecursively (LinkList* head) {if (NULL = = head) return Else {RPrintListRecursively (head- > next); printf ("% d", head- > value);}} 6. Sort the elements of a single linked list

Because the single linked list can only get the next element through its next pointer, the sorting of the single linked list can only be sorted by traversing backwards, such as the improvement of bubble sorting. You can't use algorithms that need to look forward, such as insert sort, quick sort, and so on. The following algorithm is carried out using bubble sorting. One-trip sort places the largest element of the unsorted subsequence in the header of the sorted subsequence of the linked list (this maximum element is the minimum value in the sorted subsequence).

/ Bubble sorted single linked list LinkList* Sort (LinkList* head) {if (NULL = = head) return head; int length = Length (head); int unorder_size = length; int flag = 1; while (flag) {flag = 0; LinkList* p = head; for (int I = 0; p-> next & & I)

< unorder_size; ++i) { if (p->

Value > p-> next- > value) {int temp = p-> value; p-> value = p-> next- > value; p-> next- > value = temp; flag = 1 } p = p-> next;}-- unorder_size;} return head;} 7. Flip of a single linked list

Traverse the original list from beginning to end, one node at a time, and put it at the front end of the new list. Note that the linked list is empty and there is only one node. The time complexity is O (n).

/ / flip single linked list LinkList* ReverseList (LinkList* head) {/ / in fact, it is not necessary for if to judge when the number of nodes in the linked list is less than two, because the later program contains the judgment if (NULL = = head | | NULL = = head- > next) {return head;} LinkList* reverse_head = NULL. / / the header pointer LinkList* pcurrent = head; / / pcurrent traverses the linked list while (pcurrent) {LinkList* temp = pcurrent; pcurrent = pcurrent- > next; temp- > next = reverse_head; reverse_head = temp;} return reverse_head;} 8. Find the penultimate node in a single linked list (k > 0)

The easiest way to think of: first count the number of nodes in a single linked list, and then find the (nmurk) node. Note that when the linked list is empty, k is 0, k is 1, and k is greater than the number of nodes in the linked list. The time complexity is O (n).

Another way of thinking: you only need to traverse the single linked list once.

The main idea is to use two pointers, first let the front pointer go to the positive k node, so that the distance difference between the front and back pointers is kmurl 1, and then the front and back pointers go forward together, when the front pointer goes to the last node, the node pointed to by the back pointer is the last node.

Note that the number of linked list nodes is less than k.

/ / find the k-last node of the linked list (k > 0) LinkList * GetRKthNode (LinkList * head, int k) {if (k)

< 1 || NULL == head) return NULL; LinkList *first = head; LinkList *second = head; //如果节点个数小于k返回NULL for (int i = 1; i < k; ++i) { if (second->

Next) second = second- > next; else return NULL } / / both pointers move at the same time until the fast second pointer reaches the last node, and / / the slow first pointer points to the last node while (second- > next! = NULL) {first = first- > next; second = second- > next;} return first;} 9. Find the middle node of a single linked list

This question can be applied to a similar idea in the previous one. It also sets two pointers, but here, the two pointers go forward at the same time, the front pointer takes two steps at a time, the back pointer takes one step at a time, and when the front pointer reaches the last node, the back pointer refers to the middle node: the n / 2 + 1 node.

When the number of elements in the linked list is even, the code returns nmax 2 + 1 nodes, which should be discussed: maybe you need to return the middle two nodes or their average.

Note that the linked list is empty and the number of linked list nodes is 1 and 2. Time complexity O (n):

/ / returns the middle node of a single linked list, when the number of linked list nodes is even / / this function returns the n / 2 + 1 node LinkList* GetMiddleNode (LinkList* head) {/ / the linked list is empty or there is only one node if (NULL = = head | | NULL = = head- > next) return head; LinkList* first = head; LinkList* second = head While (second- > next) {first = first- > next; second = second- > next; if (second- > next) {/ / when the number of nodes is even, second = second- > next;}} return first;} 10. Merge two ordered single linked lists

So that the linked list is still in order after the merge, and the following code retains elements with the same value. ****

This is similar to merge sorting. Pay particular attention to situations where both linked lists are empty and when one of them is empty. Only O (1) space is needed. The time complexity is O (max (len1, len2)).

/ / merge two ordered single linked lists: non-recursive / / the original equivalent elements of the linked list retain LinkList* MergeList (LinkList* heada, LinkList* headb) {if (NULL = = heada) return headb; if (NULL = = headb) return heada; LinkList* head_merge = NULL / / compare the size of the first node, and take the smaller as the first node if (heada- > value value) {head_merge = heada; / / Note that the order of the following two statements cannot be changed, otherwise heada will point to empty heada = heada- > next;} else {head_merge = headb / / Note that the order of the following two statements cannot be changed, otherwise headb will point to empty headb = headb- > next; / / head_merge- > next = NULL;} head_merge- > next = NULL; LinkList * pmerge = head_merge While (heada! = NULL & & headb! = NULL) {if (heada- > value value) {pmerge- > next = heada; heada = heada- > next; pmerge = pmerge- > next } else {pmerge- > next = headb; headb = headb- > next; pmerge = pmerge- > next;} pmerge- > next = NULL } if (heada) pmerge- > next = heada; else if (headb) pmerge- > next = headb; return head_merge;} / / merge two ordered single linked lists: the original equivalent elements of the recursive / / linked list retain LinkList* MergeListRecursively (LinkList* heada, LinkList* headb) {if (NULL = = heada) return headb If (NULL = = headb) return heada; LinkList * head_merge = NULL; if (heada- > value value) {head_merge = heada; head_merge- > next = MergeListRecursively (heada- > next, headb);} else {head_merge = headb Head_merge- > next = MergeListRecursively (heada, headb- > next);} return head_merge;} 11. Determine whether there is a ring in a single linked list

Two pointers are also used here. If there are rings in a linked list, that is to say, traversing with a pointer, it will never come to an end. Therefore, we can traverse with two pointers, one pointer taking two steps at a time, and one pointer taking one step at a time. If there is a ring, the two pointers will definitely meet in the ring. The time complexity is O (n).

/ / determine whether there is a ring bool HasCircle (LinkList * head) {if (NULL = = head) return false; LinkList * first = head; LinkList * second = head; while (first & & second- > next) {second = second- > next- > next; first = first- > next in the linked list If (first = = second) return true;} return false;} 12. Judge whether two single linked lists intersect

If two linked lists intersect at a node, then all nodes after that intersection are common to the two linked lists. That is, if two linked lists intersect, then the last node must be common. First traverse the first linked list, remember the last node, then traverse the second linked list, and compare it with the last node of the first linked list. If it is the same, it intersects, otherwise it does not intersect. The time complexity is O (len1+len2), because only one extra pointer is needed to hold the last node address, and the space complexity is O (1).

/ / determine whether two linked lists intersect bool IsCross (LinkList* heada, LinkList* headb) {if (NULL = = heada | | NULL = = headb) return false; LinkList* taila = heada; LinkList* tailb = headb; while (taila- > next) taila = taila- > next; while (tailb- > next) tailb = tailb- > next; return taila = = tailb;} 13. Find the first node at the intersection of two single linked lists

Iterate through the first linked list, calculate the length len1, and save the address of the last node.

My idea is to assume that there is a version field in the linked list with an initial value of 0; first iterate through the first linked list, then + 1 for the version field in each linked list node, then iterate through the second linked list for the value + 1 of each version field, and when the value is found to be 2, the first node is found.

Traverse the second linked list, calculate the length len2, and check whether the last node is the same as the last node of the first linked list.

Both linked lists start from the top node, assuming that len1 is greater than len2, then the first linked list first traverses the len1-len2 nodes, and then the distance between the current node of the two linked lists and the first intersection node is equal, and then traverse backwards together, knowing that the addresses of the two nodes are the same.

Time complexity, O (len1+len2).

/ / find the first node LinkList* GetFirstCrossNode (LinkList* heada, LinkList* headb) {if (NULL = = heada | | NULL = = headb) return NULL; int lengtha = 1; LinkList* taila = heada; while (taila- > next) {+ + lengtha; taila = taila- > next;} int lengthb = 1 LinkList* tailb = headb; while (tailb- > next) {+ + lengthb; tailb = tailb- > next;} / / two linked lists do not intersect if (taila! = tailb) return NULL; LinkList* plong = heada; / / points to the long linked list LinkList* pshort = headb / / point to the small linked list int diff; if (lengthb > lengtha) {diff = lengthb-lengtha; plong = headb; pshort = heada;} / / the long linked list goes forward first, so that the two linked lists are aligned with for (int I = 0; I

< diff; ++i) plong = plong->

Next; while (plong & & pshort & & plong! = pshort) {plong = plong- > next; pshort = pshort- > next;} return plong;} 14. It is known that there is a ring in a single linked list, find the first node in the ring.

First determine whether there is a ring, if there is no end. Break at a node in the ring (of course, the original linked list cannot be destroyed at the end of the function), so that two intersecting single linked lists are formed, and the first node entering the ring is transformed into the first node finding the intersection of two single linked lists.

/ / given that there are rings in the linked list, find the first node in the linked list, LinkList* GetFirstCircleNode (LinkList* head) {if (NULL = = head) return NULL; / / to determine whether the two linked lists have rings. No ring returns empty LinkList* first = head; LinkList* second = head; while (first & & second- > next) {first = first- > next Second = second- > next- > next; if (first = = second) break;} if (NULL = = first | | NULL = = second- > next) return NULL / / take this node in the encounter ring as the hypothetical tail node, / / change the original linked list into two intersecting single linked lists, and the first common node is the LinkList* assumed_tail = first; LinkList* head1 = head; LinkList* head2 = assumed_tail- > next; LinkList* pa = head1; int length2 = 1. While (pa! = assumed_tail) {pa = pa- > next; + + length2;} LinkList* pb = head2; int length3 = 1; while (pb! = assumed_tail) {pb = pb- > next; + + length3;} pa = head1; pb = head2 If (length2 > length3) {int diff = length2-length3; while (diff--) pa = pa- > next;} else {int diff = length3-length2; while (diff--) pb = pb- > next } while (pa! = pb) {pa = pa- > next; pb = pb- > next;} return pa;} 15. Delete the node pointed to by a pointer, time complexity O (1)

For deleting a node, our common idea is to make the previous node of the node point to the next node of the node. In this case, we need to traverse to find the previous node of the node, and the time complexity is O (n). For linked lists, the structure of each node in the linked list is the same, so we can copy the data of the next node of that node to that node, and then delete the next node.

Pay attention to the case of the last node, which can only be operated in the common way, finding the previous node first, but the overall average time complexity is still O (1). The reference code is as follows:

/ / Delete the node pointed to by a pointer. Time complexity O (1) void DeleteTheNode (LinkList * head, LinkList * to_delete) {if (NULL = = to_delete | | NULL = = head) return / / the last node to be deleted is if (NULL = = to_delete- > next) {if (head = = to_delete) {/ / the only node in the linked list is head = NULL; free (to_delete); to_delete = NULL / / prevent dangling pointer} else {/ / the linked list has multiple nodes. To delete the tail node LinkList* p = head; while (p-> next! = to_delete) p = p-> next; p-> next = NULL Free (to_delete); to_delete = NULL; / / prevent dangling pointer}} else {/ / it is not the tail node to be deleted LinkList * pnext = to_delete- > next; to_delete- > value = pnext- > value To_delete- > next = pnext- > next; free (pnext); pnext = NULL;} 16. Partial test code int main () {/ * LinkList * head = BuildList (); head = InsertToHead (9, head); head = InsertToTail (100,head); head = DeletebyValue (2, head); printf ("length:% d\ n", Length (head)); PrintList (head); head = Sort (head); printf ("list1:"); PrintList (head) * / / * head = ReverseList (head); PrintList (head); * / * LinkList* kth = GetRKthNode (head, 1); if (kth) printf ("1th:%d\ n", kth- > value); * / * LinkList* mid = GetMiddleNode (head); if (mid) printf ("mid:% d\ n", mid- > value) * / / * RPrintListRecursively (head); printf ("\ n"); RPrintList (head); * / / LinkList * head = BuildList (); / / LinkList * headb = BuildList (); / / printf ("list2:"); PrintList (headb); / / LinkList * head_merge = MergeList (head, headb); / LinkList * head_merge = MergeListRecursively (head, headb) / / printf ("list merge:"); PrintList (head_merge); / * / LinkList* head = (LinkList*) malloc (sizeof (LinkList)); / / head- > next = head; LinkList* head = BuildList (); LinkList* temp = head; while (temp- > next) temp = temp- > next; temp- > next = head If (HasCircle (head)) {printf ("yes\ n");} else printf ("no\ n"); * / * LinkList* head = BuildList (); LinkList* temp = head; while (temp- > next) temp = temp- > next; LinkList* headb = BuildList () Temp- > next = headb- > next- > next; LinkList* p = GetFirstCrossNode (head, headb); if (p) printf ("% d\ n", p-> value); * /} "what are the common algorithms of linked lists"? thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.