DS：链表操作_非递减单链表的合并操作实验小结

本周DS的课后作业，写了没多久
花了比较多的时间找第一题的bug
总结：一定要把思路理清楚再动手写?

合并两个非递减链表为非递增链表

思路非常清晰的一题，先合并为非递减链表，再反转即可
合并时可以想像其过程，要点在每次判断需要合并的个数
反转参考了网络，要记住方法

#include<iostream>
using namespace std;

template<class Type>
class List;
template<class Type>
class Linknode{
    friend class List<Type>;
    public:
        Linknode(){next=NULL;}
        Linknode(const Type &value){
            data=value;
            next=NULL;
        };
    private:
        Type data;
        Linknode<Type> *next;
};
template<class Type>
class List{
    private:
        Linknode<Type> *head;
    public:
        List();
        ~List(){};
        bool create(int n);
        void show();
        Linknode<Type> *order(List a,List b);
        Linknode<Type> *reverse(Linknode<Type> *a);
        int length(List a);
    void show(Linknode<Type> *p);
};

template<class Type>
List<Type>::List()
{
    head=NULL;
 }

template<class Type>
void List<Type>::show(){
    Linknode<Type> *p=head;
    if(head==NULL) cout<<"链表为空"<<endl;
    else {
        for(;p;p=p->next)
        cout<<p->data<<"  ";}
    cout<<endl;
}

template<class Type>
void List<Type>::show(Linknode<Type> *p){
    if(p==NULL) cout<<"链表为空"<<endl;
    else {
        for(;p;p=p->next)
        cout<<p->data<<"  ";}
    cout<<endl;
}

template<class Type>
bool List<Type>::create(int n)
{   int i=0;
    head=new Linknode<Type>(NULL);
    Linknode<Type> *p=head,*q;
    if (n==0) return false;
    for (i=1;i<n;i++)
    {
        cin>>p->data;
        q=new Linknode<Type>(NULL);
        p->next=q;
        p=q;
    }
    cin>>p->data;//last node
    p->next=NULL;
    return true;
}

template<class Type>
Linknode<Type>* List<Type>::order(List a,List b)
{   int i=0;
    Linknode<Type> *pa,*pan,*pb,*pbn;
    if(a.head->data<=b.head->data) {i=1;pa=a.head;pb=b.head;}
    else {pa=b.head;pb=a.head;}
    pan=pa->next;pbn=pb->next;
    while(pan&&pbn)
    {
        if(pa->data<=pb->data) 
		{while(pan&&pbn&&(pan->data<=pb->data))
        {pa=pa->next;pan=pan->next;}
        pa->next=pb;pa=pan;pan=(pa)?pa->next:NULL;continue;}
        if(pb->data<=pa->data)
        {while(pbn&&pan&&(pbn->data<=pa->data))
        {pb=pb->next;pbn=pbn->next;}
        pb->next=pa;pb=pbn;pbn=(pb)?pb->next:NULL;}
    }
    if(pa&&!pan&&pb) {if(pb->data>=pa->data) {pa->next=pb;return i?a.head:b.head;}
	else {while(pbn&&(pbn->data<=pa->data)) 
	{pb=pb->next;pbn=pbn->next;}
	pb->next=pa;pa->next=pbn; return i?a.head:b.head;}}
    if(pb&&!pbn&&pa){
	while(pan&&(pan->data<=pb->data)) 
	{pa=pa->next;pan=pan->next;}
	pa->next=pb;pb->next=pan; return i?a.head:b.head;}
	if(!pan&&!pbn) pa->next=pb;
    return i?a.head:b.head;
}

template<class Type>
int List<Type>::length(List a)
{   Linknode<Type> *p=a.head;int i=0;
    if(p==NULL) return 0;
    while(!p){p=p->next;i++;}
    return i;
}

template<class Type>
Linknode<Type>* List<Type>::reverse(Linknode<Type> *a)
{
    Linknode<Type> *pnow,*pnext,*ppre;
    ppre=a;pnow=a->next;pnext=pnow->next;
    pnow->next=ppre;ppre->next=NULL;//first reverse
    ppre=pnow;pnow=pnext;pnext=(pnow)?pnow->next:NULL;
    while(pnow)
    {
        pnow->next=ppre;
        ppre=pnow;pnow=pnext;
        pnext=(pnow)?pnow->next:NULL;
    }
    return ppre;
}

int main()
{   int n1=0,n2=0;
    Linknode<int> *h;
    List<int> a,b;
    cout<<"输入第一个非递减链表的元素个数："<<endl;
    cin>>n1;
    cout<<"输入"<<n1<<"个整数："<<endl;
    a.create(n1);
    cin.sync();
    cout<<"输入第二个非递减链表的元素个数："<<endl;
    cin>>n2;
    cout<<"输入"<<n2<<"个整数："<<endl;
    b.create(n2);
    cout<<"================================================"<<endl;
    cout<<endl<<"第一个非递减链表："<<endl;
    a.show();
    cout<<endl<<"第二个非递减链表："<<endl;
    b.show();
    h=a.order(a,b);
    h=a.reverse(h);
    cout<<endl<<"输出排序后非递增链表："<<endl;
    a.show(h);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

判断链表中是否有环

有环返回环的第一个结点
学习了Floyd环的思路，快慢指针相遇的情况
比较难想的思路，但是适用情况不多

#include<iostream>
using namespace std;

template<class Type>
class List;
template<class Type>
class Linknode{
    friend class List<Type>;
    public:
        Linknode(){next=NULL;}
        Linknode(const Type &value){
            data=value;
            next=NULL;
        };
    private:
        Type data;
        Linknode<Type> *next;
};
template<class Type>
class List{
    private:
        Linknode<Type> *head;
    public:
        List();
        ~List(){};
        bool create(int n);
        void show();
        Linknode<Type> *loop(int n);
};

template<class Type>
List<Type>::List()
{
    head=NULL;
 }

template<class Type>
void List<Type>::show(){
    Linknode<Type> *p=head;
    if(head==NULL) cout<<"链表为空"<<endl;
    else {
        for(;p;p=p->next)
        cout<<p->data<<"  ";}
    cout<<endl;
}

template<class Type>
bool List<Type>::create(int n)
{   int i=0,x=0;
    char answer;
    head=new Linknode<Type>(NULL);
    Linknode<Type> *p=head,*q;
    if (n==0) return false;
    while(1){
	cout<<"是否建立有环链表？（Y/N)"<<endl;
    cin>>answer;
	if(answer=='N'||answer=='Y') break;
	else cout<<"选择失败，重新输入"<<endl;} 
	cout<<"输入"<<n<<"个整数："<<endl;
    for (i=1;i<n;i++)
    {
        cin>>p->data;
        q=new Linknode<Type>(NULL);
        p->next=q;
        p=q;
    }
    cin>>p->data;//last node
    if(answer=='Y'){cout<<"输入入环节点的序号："<<endl;
	cin>>x;q=head;i=1;
	while(i<x) {q=q->next;i++;}
	p->next=q;}
	else  p->next=NULL;
    return true;
}
template<class Type>
Linknode<Type>* List<Type>::loop(int n)
{
    Linknode<Type> *fast=head,*slow=head; 
    if(n==0) {cout<<"链表为空"<<endl; return NULL;}
    while(fast&&slow)
    {fast=fast->next;fast=(fast)?fast->next:NULL;
    slow=slow->next;
	if(fast==slow) 
	{cout<<"链表有环"<<endl;
	fast=head;while(fast!=slow) {fast=fast->next;slow=slow->next;}
	cout<<"环的第一个节点："<<fast->data<<endl;return fast;}
	if(!fast) {cout<<"链表无环"<<endl;return head;}
	} 
}

int main()
{
    int n1=0,n2=0;
    List<int> a;
    cout<<"输入链表的元素个数："<<endl;
    cin>>n1;
    a.create(n1);
    cout<<"================================================"<<endl;
    a.loop(n1);
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

对链表的模版类定义熟悉了很多，思路也是理清了才写的
但是对细节的思考仍然不够

• 要分类每种情况，想好解决思路