7-51 combination of two ordered linked list sequences

7-51 The combination of two ordered list sequences

subject

Two non descending linked list sequences are known S1 And S2, Design functions to construct S1 And S2 New non descending list after merging S3.
Input format :
The input is divided into two lines , In each row, a non descending sequence composed of several positive integers is given , use −1 Represents the end of a sequence （−1 Not in this sequence ）. The numbers are separated by spaces .
Output format :
Output the new non descending linked list after merging in one row , Separate numbers with spaces , There can't be extra spaces at the end ; If the new list is empty , Output NULL.
sample input :

1 3 5 -1 2 4 6 8 10 -1
No blank lines at the end

sample output :

1 2 3 4 5 6 8 10
No blank lines at the end

A lot of information , Some places refer to the ideas of bloggers .

Specific ideas

1. Set up two linked lists L1,L2, There is value , To -1 stop it .
2. Initialize the third linked list L3, Sequential comparison L1,L2 The value of the inside , Use L1,L2 The nodes inside construct the third linked list .（ Because it is not said to create a new linked list and put the value after comparing the size , This is better ）
3. Print L3.

Code implementation

#include<iostream>
#include<malloc.h> // This can't be lost 
using namespace std;

typedef struct LNode {
    
    int data;
    struct LNode* next;
}LNode, *LinkList;

// How to create multiple linked lists 
LinkList CreateList()    // Initialization and creation are combined ！
{
    
   LinkList L = (LNode*)malloc(sizeof(LNode));  // Create a header node for the first linked list 
   L->next = NULL;                             // Initially empty 
    LinkList p;
    p = L;
    int e;
    while (cin >> e)
    {
    
        if (e == -1)
            break;           *// I can't write this as return  use return You must return the corresponding value  
            				 // use break* Jump out of current loop ！
         // Tail connection 
        LinkList temp = (LNode*)malloc(sizeof(LNode));
        temp->data = e;
        temp->next = p->next;
        p->next = temp;  
        p = p->next;
    }
    return L;                    // At the end of the cycle return true  Otherwise, it will jump out of the cycle   And don't forget to add 
}

// Merge functions 
LinkList Merge(LinkList L1, LinkList L2)          // The whole incoming 
{
    
	 // initialization p3
     LinkList p3;
     LinkList L;
     L = (LNode*)malloc(sizeof(LNode));
     p3 = L;
     p3->next = NULL;
     
    LNode* p1 = L1->next; // Set up a pointer to traverse L1,L2
    LNode* p2 = L2->next;
    while (p1 && p2)
    {
    
        //LinkList temp = (LNode*)malloc(sizeof(LNode)); 
        // Not quite right , The requirement is to merge , There is no requirement to create a new linked list .
        
        if (p1->data >= p2->data)       // Just put in the equal ！
        {
    
            p3->next = p2;            // Descending order   Lenient ！
            p2 = p2->next;            // Analogy bubble sort ！！！
        }
        else {
    
            p3->next = p1;
                p1 = p1->next;
        }
        p3 = p3->next;
    }
	// After one traversal, connect the other nodes of the list that have not been traversed to the back 
      p3->next = p1 ? p1 : p2;   // The trinocular operator is very simple , The following code can also be implemented , Better understanding 
      
   // while (p1)
	//{
    
	// p3->next = p1;
	// p1 = p1->next;
	// p3 = p3->next;
	//}
	//while (p2)
	//{
    
	// p3->next = p2;
	// p2 = p2->next;
	// p3 = p3->next;
	//}
	
    L1->next = NULL;   // This is an important step ！ Let the whistle node point to empty , Disconnect from the two linked lists 
    L2->next = NULL;
    return L;
}

// Print L3
bool Print(LinkList &L3)
{
    
    LNode* p = L3;
    p = p->next;
    if(p==NULL)
    {
    
        cout << "NULL" << endl;
        return true;     // Write here false still true  It doesn't matter ！
       // break;  no way   Can only block circulation ！
    }
    while (p != NULL)
    {
     
        cout << p->data << " " ;
        p = p->next;
        if(p->next == NULL)         // Here we use the pointer to remove the extra space at the end ！
        {
    
            cout << p->data;
            //return true; // This one will do ！
            break;                 // You can use it here break！！！
        }
     // cout << endl;
    }
    return true;       // After the cycle ends return true!
}

int main()
{
    
      LinkList L1,L2,L3; // You can change three lines into one line 
	  L1 =  CreateList();
	  L2 =  CreateList();
   /* CreateList(L1); CreateList(L2);*/    // Such similar code cannot   Ambiguity ！

      L3 = Merge(L1, L2);
      Print(L3);

    return 0;
}

Some of my questions

1. How to create multiple linked lists

LinkList CreateList(), Last return L;
Main function L1 = CreateList(); L2 = CreateList(); that will do

2. How to input these numbers in sequence until -1 stop it

while(1) or while(cin >> e) To -1 Then use break

3. How to compare two single linked lists data The value of the field is stored in the linked list L3 in ?

Set two more movable pointers to traverse

4. What about equal data ?

Just put it in ！ Just put one ！

5. What if one of them finishes traversing ？

p1,p2 Itself is in descending order , Don't bother. , Directly connect the remaining nodes of the linked list to the back

6. How can I even ？

Use the ternary operator ！！ Or loop

7. summary
（1）break Usage of ： Terminate the current loop .
（2） Note whether the title requires the creation of a new linked list .
（3） Use the pointer p->next = NULL To remove the last blank .
（4） After combining to form the third linked list, let the first two linked lists point to null ！
（5） The idea of creating a pointer to a linked list is very important , Traversing the linked list , Delete node , It's useful to find a node ！

End of the flower ~！
2021.10.2
22:25