This problem requires the implementation of a function to merge the increasing integer sequence represented by two linked lists into a non decreasing integer sequence.

Function interface definition:

List Merge( List L1, List L2 );

The List structure is defined as follows:

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* Store node data */
    PtrToNode   Next; /* Pointer to the next node */
};
typedef PtrToNode List; /* Define single linked list type */

L1 and L2 are the single linked lists of the given leading nodes, and the data stored in the nodes are incrementally ordered; The function Merge combines L1 and L2 into a non decreasing sequence of integers. The node in the original sequence should be directly used to return the chain header pointer of the merged leading node.

Example of referee test procedure:

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* Details are not listed here */
void Print( List L ); /* Details are not shown here; Empty linked list will output NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* Your code will be embedded here */

Input example:

3
1 3 5
5
2 4 6 8 10

Output example:

1 2 3 4 5 6 8 10 
NULL
NULL

The basic idea of this question is

1) Constantly compare the current pointer element size of the linked list, and move the smaller one into the consolidated linked list

2) At the same time, the smaller linked list pointer moves back p=p->next, and the merged linked list pointer moves back l=l->next at the same time

It is worth noting that each operation will connect all parts of the linked list from the pointer to the following parts into the consolidated linked list, but each position will be continuously updated by the following operations, and finally ensure that each bit is judged.

When the pointer of one of L1 and L2 has moved to the end, the loop exits.

Finally, you only need to connect the rest of the list that has not been traversed directly to the merged list.

L->next=p?p:q;

There is also a hidden hole in this problem: after merging the linked lists, the merged two linked lists should be set to empty.

L1->next=NULL;L2->next=NULL;

List Merge( List L1, List L2 )
{
	List L3=(List)malloc(sizeof(Node));
	List L=L3;
	List p=L1->Next;List q=L2->Next;
	while(p&&q)
	{
		if(p->Data<=q->Data)
		{
			L->Next=p;
			p=p->Next;
		}
		else
		{
			L->Next=q;
			q=q->Next;
		}
		L=L->Next;
	}
	L->Next=p ? p : q;
    L1->Next=NULL; 
    L2->Next=NULL;
    return L3;
}