代码题均来自B站up：白话拆解数据结构。
今日习题：
（1）将两个递增的有序链表合并为一个递增的有序链表，不能有重复的元素，不能占用其他内存空间；
（2）将带头单链表A分解为带头节点的单链表A和B，使得A表含原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持相对元素不变；
（3）将（2）中的单链表A还是拆分成两个表，但在上述条件下，保持a表不变，b表元素逆置。
题1
第一题和昨天第二题那道题完全一样，就是多了一个要求：不能有重复的元素，删除掉就行了。
Linklist sort_2to1list(Linklist &L1,Linklist &L2){
Lnode *p,*q;
p=L1->next;
q=L2->next;
while(q){
Lnode *p_pre=L1;
Lnode *q_next=q->next;
p=L1->next;
while(p&&p->data<q->data){ //找插入位置
p_pre=p;
p=p->next;
}
q->next=p;
p_pre->next=q;
q=q_next;
} //上面部分代码和昨天完全一致
Lnode *s=L1,*t=L1->next;
while(t){ // 找重复值
if(s->data==t->data){
s->next=t->next;
free(t);
t=s->next;
}else{
s=s->next;
t=t->next;
}
}
L2->next=NULL;
return L1;
}
我这里把值重复的单独做了删除操作，也有简便的写法。
Linklist sort_2to1list(Linklist &L1,Linklist &L2) {
Lnode *p, *q;
p = L1->next;
q = L2->next;
while(q) {
Lnode *p_pre = L1;
Lnode *q_next = q->next; // 保存 q 的下一个节点
p = L1->next;
// 找到合适的位置插入 q
while (p && p->data < q->data) {
p_pre = p;
p = p->next;
}
// 如果在适当的位置插入 q
if (!p || p->data != q->data) {
q->next = p_pre->next;
p_pre->next = q;
} else {
// 如果有相同的数据，直接跳过，不插入重复元素
free(q); // 释放 q 节点的内存
}
q = q_next; // 继续处理下一个 q 节点
}
// 不需要再额外进行去重，因为插入时已经去重
L2->next = NULL;
return L1;
}
实践：
完整代码如下：
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
// 单链表结构体定义
typedef struct Lnode{
int data;
Lnode *next;
}Lnode,*Linklist;
Linklist list_insertbytail(Linklist &L){
Lnode *s;
int x;
L = (Lnode*)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *r = L;
cin >> x;
while(x!=9999){
s = (Lnode*)malloc(sizeof(Lnode));
s->data=x;
s->next=NULL;
r->next = s;
r=r->next;
cin >> x;
}
return L;
}
// 将两个递增的有序链表合并为一个递增的有序链表，不能有重复的元素，不能占用其他内存空间
Linklist sort_2to1list(Linklist &L1,Linklist &L2){
Lnode *p,*q;
p=L1->next;
q=L2->next;
while(q){
Lnode *p_pre=L1;
Lnode *q_next=q->next;
p=L1->next;
while(p&&p->data<q->data){ //找插入位置
p_pre=p;
p=p->next;
}
q->next=p;
p_pre->next=q;
q=q_next;
} //上面部分代码和昨天完全一致
Lnode *s=L1,*t=L1->next;
while(t){ // 找重复值
if(s->data==t->data){
s->next=t->next;
free(t);
t=s->next;
}else{
s=s->next;
t=t->next;
}
}
L2->next=NULL;
return L1;
}
//另一种写法，简洁
Linklist sort_2to1list(Linklist &L1,Linklist &L2) {
Lnode *p, *q;
p = L1->next;
q = L2->next;
while(q) {
Lnode *p_pre = L1;
Lnode *q_next = q->next; // 保存 q 的下一个节点
p = L1->next;
// 找到合适的位置插入 q
while (p && p->data < q->data) {
p_pre = p;
p = p->next;
}
// 如果在适当的位置插入 q
if (!p || p->data != q->data) {
q->next = p_pre->next;
p_pre->next = q;
} else {
// 如果有相同的数据，直接跳过，不插入重复元素
free(q); // 释放 q 节点的内存
}
q = q_next; // 继续处理下一个 q 节点
}
// 不需要再额外进行去重，因为插入时已经去重
L2->next = NULL;
return L1;
}
int main(){
Linklist L1,L2;
list_insertbytail(L1);
list_insertbytail(L2);
Lnode *p = L1->next;
Lnode *q = L2->next;
printf("origin listL1:");
while (p != NULL) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
printf("origin listL2:");
while (q != NULL) {
printf("%d ",q->data);
q = q->next;
}
printf("\n");
sort_2to1list(L1,L2);
printf("new list:");
Lnode *qs = L1->next;
while (qs != NULL) {
printf("%d-> ",qs->data);
qs = qs->next;
}
printf("NULL");
return 0;
}题2
直接带着代码看吧！
Linklist Decompose(Linklist &L){
if(!L||!L->next) return L;
Linklist L2; // 新建一个头结点
L2 = new Lnode;
L2->next=NULL;
Lnode *p,*q,*r,*s; // 定义一些工作指针
p=L->next;
q=p->next;
L2->next=q;
p->next=NULL; // 断开，作为表1
r=q->next;
q->next=NULL; // 断开，作为表2
int i =1; // 记录奇数还是偶数
if(!r) return L2; //
while(r){ // r指针用来遍历还未插入的链表部分
s=r->next; // 每次循环更新s指针，s指针始终指向r指针的后面
if(i%2==1){
p->next=r;
r->next=NULL; // 断开它，不然两个链表会交叉着链接
p=p->next;
}
else
{
q->next=r;
r->next=NULL; // // 断开它，不然两个链表会交叉着链接
q=q->next;
}
r=s; // 更新r指针和计数器
i++;
}
return L2; // 返回表2即可，L1加了引用会保持这种改变
}
由于是一个表变成两个带头结点的表，所以要先创建第二个表的头结点，然后初始化一些指针，如下图：
这样的做法就是默认链表最少有两个结点，然后从第三个结点开始（第三个结点是单数开始），然后单数连L，偶数连L2
这里展示一下连4结点的操作（奇数结点）：就是if里面的语句
演示结束，实践一下：
看看特殊情况，就是我们定的规矩，3个结点的情况：
代码如下：
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
// 单链表结构体定义
typedef struct Lnode{
int data;
Lnode *next;
}Lnode,*Linklist;
Linklist list_insertbytail(Linklist &L){
Lnode *s;
int x;
L = (Lnode*)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *r = L;
cin >> x;
while(x!=9999){
s = (Lnode*)malloc(sizeof(Lnode));
s->data=x;
s->next=NULL;
r->next = s;
r=r->next;
cin >> x;
}
return L;
}
// 将带头单链表A分解为带头节点的单链表A和B，使得A表含原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持相对元素不变
Linklist Decompose(Linklist &L){
if(!L||!L->next) return L;
Linklist L2;
L2 = new Lnode;
L2->next=NULL;
Lnode *p,*q,*r,*s;
p=L->next;
q=p->next;
L2->next=q;
p->next=NULL;
r=q->next;
q->next=NULL;
int i =1;
if(!r) return L2;
while(r){
s=r->next;
if(i%2==1){
p->next=r;
r->next=NULL;
p=p->next;
}
else
{
q->next=r;
r->next=NULL;
q=q->next;
}
r=s;
i++;
}
return L2;
}
int main(){
Linklist L;
list_insertbytail(L);
Lnode *p = L->next;
printf("origin list:");
while (p != NULL) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
Lnode *q=Decompose(L);
printf("new L1:");
Lnode *s = L->next;
while (s != NULL) {
printf("%d-> ",s->data);
s = s->next;
}
printf("NULL");
printf("\n");
printf("new list L2:");
while (q ->next!= NULL) {
printf("%d-> ",q->next->data);
q = q->next;
}
printf("NULL");
return 0;
}题3
和题2差不多，很相似，偶数表采用头插法就行了，easy。
Linklist Decompose2(Linklist &L){
if(!L||!L->next) return L;
Linklist L2;
L2 = new Lnode;
L2->next=NULL;
Lnode *p,*q,*r,*s;
p=L->next;
q=p->next;
L2->next=q;
p->next=NULL;
r=q->next;
q->next=NULL;
int i =1;
if(!r) return L2;
while(r){
s=r->next;
if(i%2==1){
p->next=r;
r->next=NULL;
p=p->next;
} // 上述都一致
else
{ // 头插法
L2->next=r;
r->next=q;
q=r;
}
r=s;
i++;
}
return L2;
}
实践一下：
看看特殊情况：三个结点
代码如下：
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
// 单链表结构体定义
typedef struct Lnode{
int data;
Lnode *next;
}Lnode,*Linklist;
Linklist list_insertbytail(Linklist &L){
Lnode *s;
int x;
L = (Lnode*)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *r = L;
cin >> x;
while(x!=9999){
s = (Lnode*)malloc(sizeof(Lnode));
s->data=x;
s->next=NULL;
r->next = s;
r=r->next;
cin >> x;
}
return L;
}
// 还是拆分成两个表，a表不变，b表逆置
Linklist Decompose2(Linklist &L){
if(!L||!L->next) return L;
Linklist L2;
L2 = new Lnode;
L2->next=NULL;
Lnode *p,*q,*r,*s;
p=L->next;
q=p->next;
L2->next=q;
p->next=NULL;
r=q->next;
q->next=NULL;
int i =1;
if(!r) return L2;
while(r){
s=r->next;
if(i%2==1){
p->next=r;
r->next=NULL;
p=p->next;
}
else
{
L2->next=r;
r->next=q;
q=r;
}
r=s;
i++;
}
return L2;
}
int main(){
Linklist L;
// list_insertbyhead(L);
list_insertbytail(L);
Lnode *p = L->next;
printf("origin list:");
while (p != NULL) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
Lnode *q=Decompose2(L);
printf("new L1:");
Lnode *s = L->next;
while (s != NULL) {
printf("%d-> ",s->data);
s = s->next;
}
printf("NULL");
printf("\n");
printf("new list L2:");
while (q ->next!= NULL) {
printf("%d-> ",q->next->data);
q = q->next;
}
printf("NULL");
return 0;
}