©2020-2024 ioDraw All rights reserved
One , Topic requirements
* Now there are 2 Single list , They're all in order （ from small to large ）, Now I want you to merge two single linked lists into 1 Single list , After the merger, the linked list is still in order
* for example ：
* list1 by 1,3,5
* list2 by 2,4,6
* take list1 and list2 Merge into new linked list list3, The value is 1,2,3,4,5,6
Two , Coding implementation
/** * @description: take temp Node inserted into head In the linked list * @param: head: The starting position of the linked list to insert temp:
The node pointer of the linked list to insert * @return: Returns the head node of the inserted linked list * @author: Dongshao */ Node
*insert_node(Node *head, Node *temp) { Node *p = head; Node *q = NULL; //
as long as q No p The value of the node is small , Then go back and forth while(p->_data < temp->_data && p != NULL) { q = p; p =
p->_pNext; } // If p be equal to head, explain temp than head All the nodes in the linked list are small , So will temp Insert into head before ,
Direct return temp That's fine if(p == head) { temp->_pNext = p; return temp; } //
Otherwise, it will temp Insert into head In the middle of the linked list q->_pNext = temp; temp->_pNext = p; return head; } /**
* @description: Merge two ordered linked lists ( from small to large ) * @param : list1: The first 1 Linked list list2: The first 2 Linked list * @return:
Returns the head node of the merged linked list * @author: Dongshao */ Node *merge2List(Node *list1, Node *list2) {
// If which list is empty , Then return to another linked list if (list1 == NULL) return list2; if (list2 == NULL)
return list1; Node *head; // Start with a long list Node *p; // Start with a shorter list Node *q; //
Direction and p Node after // Linked list 1 Comparison list 2 long if (listLength(list1) >= listLength(list2)) { head =
list1->_pNext; p = list2->_pNext; } else { head = list2->_pNext; p =
list1->_pNext; } // Which list is short , Just loop which short list to insert into the long list while (p != NULL) { q = p->_pNext;
// Save next node first head = insert_node(head, p); // take p Insert into head In the linked list p = q; } //
Returns the head node of the newly formed linked list return head; } /** * @description: Returns the length of the linked list * @param: _head: Head node of linked list
* @return: Returns the length of the linked list * @author: Dongshao */ size_t listLength(Node *_head) { if
(_head == NULL || _head->_pNext == NULL) return 0; size_t count; Node *temp =
_head->_pNext; while (temp != NULL) { count++; temp = temp->_pNext; } return
count; }
Three , test
* The test code is as follows #include <stdio.h> #include <stdlib.h> typedef struct node { struct
node *_pNext; int _data; } Node; Node *insert_node(Node *head, Node *temp);
Node *merge2List(Node *list1, Node *list2); Node *createList(int num); void
showList(Node *_head); size_t listLength(Node *_head); void freeList(Node
*_head); /** * @description: take temp Node inserted into head In the linked list * @param: head: The starting position of the linked list to insert
temp: The node pointer of the linked list to insert * @return: Returns the head node of the inserted linked list * @author: Dongshao */ Node
*insert_node(Node *head, Node *temp) { Node *p = head; Node *q = NULL; //
as long as q No p The value of the node is small , Then go back and forth while(p->_data < temp->_data && p != NULL) { q = p; p =
p->_pNext; } // If p be equal to head, explain temp than head All the nodes in the linked list are small , So will temp Insert into head before ,
Direct return temp That's fine if(p == head) { temp->_pNext = p; return temp; } //
Otherwise, it will temp Insert into head In the middle of the linked list q->_pNext = temp; temp->_pNext = p; return head; } /**
* @description: Merge two ordered linked lists ( from small to large ) * @param : list1: The first 1 Linked list list2: The first 2 Linked list * @return:
Returns the head node of the merged linked list * @author: Dongshao */ Node *merge2List(Node *list1, Node *list2) {
// If which list is empty , Then return to another linked list if (list1 == NULL) return list2; if (list2 == NULL)
return list1; Node *head; // Start with a long list Node *p; // Start with a shorter list Node *q; //
Direction and p Node after // Linked list 1 Comparison list 2 long if (listLength(list1) >= listLength(list2)) { head =
list1->_pNext; p = list2->_pNext; } else { head = list2->_pNext; p =
list1->_pNext; } // Which list is short , Just loop which short list to insert into the long list while (p != NULL) { q = p->_pNext;
// Save next node first head = insert_node(head, p); // take p Insert into head In the linked list p = q; } //
Returns the head node of the newly formed linked list return head; } /** * @description: Create linked list * @param: num: Number of nodes in linked list *
@return: Head pointer to create a new linked list * @author: Dongshao */ Node *createList(int num) { if (num <
0) return NULL; Node *_head = (Node *)malloc(sizeof(Node)); _head->_pNext =
NULL; Node *_tempHead = _head; Node *_newNode; for (int i = 0; i < num; ++i) {
// Create a new node _newNode = (Node *)malloc(sizeof(Node)); _newNode->_data = (i + 1);
_newNode->_pNext = NULL; // Offset backward _tempHead->_pNext = _newNode; _tempHead =
_newNode; _newNode = NULL; } return _head; } /** * @description: Print linked list * @param:
_head: Head node of linked list * @return: nothing * @author: Dongshao */ void showList(Node *_head) {
if (_head == NULL) return; Node *_tempNode = _head; // Circular printing while (_tempNode !=
NULL) { if (_tempNode->_pNext == NULL) break; else printf("%d->",
_tempNode->_data); _tempNode = _tempNode->_pNext; } // Print the printf("%d\n",
_tempNode->_data); } /** * @description: Returns the length of the linked list * @param: _head: Head node of linked list *
@return: Returns the length of the linked list * @author: Dongshao */ size_t listLength(Node *_head) { if
(_head == NULL || _head->_pNext == NULL) return 0; size_t count; Node *temp =
_head->_pNext; while (temp != NULL) { count++; temp = temp->_pNext; } return
count; } /** * @description: Destroy linked list * @param: _head: Head node of linked list * @return: nothing *
@author: Dongshao */ void freeList(Node *_head) { if (_head == NULL ||
_head->_pNext == NULL) return; Node *temp1 = _head->_pNext; Node *temp2; while
(temp1 != NULL) { temp2 = temp1->_pNext; free(temp1); temp1 = temp2; } } int
main() { Node *list1 = NULL, *list2 = NULL; // Create linked list , And print the linked list list1 =
createList(3); list2 = createList(3); // Forgery of the first list , Change its value to 1,3,5
list1->_pNext->_data = 1; list1->_pNext->_pNext->_data = 3;
list1->_pNext->_pNext->_pNext->_data = 5; // Forgery of the second linked list , Change its value to 2,4,6
list2->_pNext->_data = 2; list2->_pNext->_pNext->_data = 4;
list2->_pNext->_pNext->_pNext->_data = 6; showList(list1->_pNext);
showList(list2->_pNext); // Reverse linked list , And print the linked list Node *list3 = merge2List(list1, list2);
showList(list3); // Release linked list freeList(list1); freeList(list2); return 0; }
* give the result as follows ：
Technology