课后习题 2-15 有序表逆序合并（单链表重点算法）

#pragma once
#include<iostream>
using namespace std;

class LNode {
public:
    int data;
    LNode* next;
};

class LinkList {
public:
    LNode* first;

    LinkList() {
        first = new LNode();
        first->data = 666;
        first->next = nullptr;
    }
    void creatE(int arr[], int n) {
        LNode* p;
        LNode* s;
        p = first;
        for (int i = 0; i < n; i++) {
            s = new LNode();
            s->data = arr[i];
            p->next = s;
            p = s;
        }
    }
    void show() {
        LNode* p;
        p = first->next;
        while (p != nullptr) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    void unite(LinkList B) {
        //先合并
        LNode* ha = first;
        LNode* hb = B.first;  //题目要求头指针为ha、hb
        LNode* p = ha->next;
        LNode* q = hb->next;
        LNode* s;
        while (q->next != nullptr && p->next != nullptr) {
            if (q->data >= p->data && q->data <= p->next->data) {
                s = q;
                q = q->next;
                s->next = p->next;
                p->next = s;
            }
            else {
                p = p->next;
            }
        }
        if (p->next == nullptr && q != nullptr) {
            p->next = q;
        }

        //开始逆序
        /**
        单链表的逆序的算法思路：
        (head)->(1)->(2)->(3)->(4)->NULL
        step 1:
        创建3个结点指针。因为单链表的单向性，3个指针一个都不能少
        LNode *p1=head->next,*p2=p1->next,*p3=p2->next;
        (head)->(1/p1)->(2/p2)->(3/p3)->(4)->NULL

        step 2:
        p1先指向null
        p1->next=nullptr;
        NULL<-(1/p1)  (2/p2)->(3/p3)->(4)->NULL (head)->(1)

        step 3:
        循环，改变指针指向
        while(p3!=nullptr){
            p2->next=p1;
            p1=p2;
            p2=p3;
            p3=p3->next;
        }
            第一次循环后：
            NULL<-(1)<-(2/p1)  (3/p2)->(4/p3)->NULL (head)->(1)
            第二次循环后：
            NULL<-(1)<-(2)<-(3/p1)  (4/p2)->NULL/p3 (head)->(1)

        step 4:
        处理最后一组指针并解决头结点
        p2->next=p1;
        head=p2;
        NULL<-(1)<-(2)<-(3/p1)<-(4/p2)<-(head)  NULL/p3
        */

        LNode* p1;
        LNode* p2;
        LNode* p3;
        p1 = ha->next;
        p2 = p1->next;
        p3 = p2->next;
        p1->next = nullptr;
        while (p3 != nullptr) {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            p3 = p3->next;
        }
        p2->next = p1;
        ha->next = p2;
    }

};

#include"LinkList.h"
int main() {
    int a[] = { 1,3,5,7,9 };
    int b[] = { 2,2,4,4,6,6,8,8,10,10 };
    LinkList A, B;
    A.creatE(a, 5);
    B.creatE(b, 10);
    A.unite(B);
    A.show();
    return 0;
}