将两链表合并且不申请新节点


/*7.递增有序单链表L1、L2，不申请新结点，利用原表结点对两表进行合并，
并使得合并后成为一个集合，合并后用L1的头结点作为头结点，删除多余的结点，删除L2的头结点。
要求时间性能最好。实验测试数据基本要求： 
第一组
第一个单链表元素为 （1，3，6，10，15，16，17，18，19，20）
第二个单链表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30）
第二组
第一个单链表元素为 （1，3，6，10，15，16，17，18，19，20）
第二个单链表元素为 （2，4，5，7，8，9，12，22）
第三组
第一个单链表元素为 （）
第二个单链表元素为 （1，2，3，4，5，6，7，8，9，10）
*/
#include <iostream>
#include<stdlib.h>
using namespace std;
#define max 100
typedef int element;
typedef struct slNode {
    element data;
    struct slNode* next;
}node, * linkList;
void initialList(node*& L) {
    L = new node;
    L->next = NULL;
}
 
void listUnion(node* L1, node* L2) {
    node* p = L1;//p指向L1头结点
    node* q = L2;//q指向L2头结点
    node* m = L1->next;//m指向L1首元素结点
    node* n = L2->next;//n指向L2首元素结点
     while (m!=NULL&&n!=NULL) {
        if (m->data == n->data) {
            p = p->next;
            q = q->next;
            m = m->next;
            n = n->next;
         }
        else if (m->data < n->data) {
            p = p->next;
            m = m->next;
        }
        else {
            q ->next= n->next;
            p->next = n;
            n->next = m;
            p = p->next;
            n = q->next;
        }
    }
    if (m == NULL) {//如果L1先遍历完
        p->next = q->next;
    }
    delete p;
    delete L2;
}
void listAdd(node*& L) {//输入一组元素
    element x = 0;
    node* u ;
    node* p = L;
     cin >> x;
    while (x != 9999) {
        u = new node;
        u->data = x;
        u->next = NULL;
        p->next = u;
        p = p->next;
        cin >> x;
    }
 }

void listPrint(node* L) {
     node* p = L->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
}
int main() {
    node* L1, * L2;
    initialList(L1);
    initialList(L2);
    cout << "输入L1中元素：";
    listAdd(L1);
    cout << "输入L2中元素：";
     listAdd(L2);
    listUnion(L1, L2);
    listPrint(L1);
}