习题来自B站up：白话拆解数据结构!
题目如下：
（1）在递增有序的单链表L中，删除值重复的结点
（2）使带头节点单链表的值递增有序
题1
和之前顺序表那题差不多，因为是有序的，所以值重复的必定挨着，首先要有一个指针来遍历链表，还需要一个指针在该指针的前面，一是用来比较相邻值的大小，而是充当前驱指向删除操作。
Linklist del_same(Linklist &L){
if (!L || !L->next) return L; // 边界条件判断
Lnode *p,*q; // 提到的俩指针
p=L->next;
q=p->next;
while(q){
if(p->data==q->data){
p->next=q->next; //删除操作
free(q);
q=p->next;
}
else{
p=p->next;
q=q->next;
}
}
return L;
}
实践：
完整代码如下：
#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;
}// 在递增有序的单链表L中，删除值重复的结点
Linklist del_same(Linklist &L){if (!L || !L->next) return L;Lnode *p,*q;p=L->next;q=p->next;while(q){if(p->data==q->data){p->next=q->next;free(q);q=p->next;}else{p=p->next;q=q->next;}}return L;
}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");del_same(L);printf("new list:");Lnode *q = L->next;while (q != NULL) {printf("%d-> ",q->data);q = q->next;}printf("NULL");return 0;
}题2
这个题需要借助直接插入排序的思想，将链表的第一个结点next域置为空，将第一个元素视为有序区，断开的链表视为无序区，每次将无序区的一个链表结点插入到有序区中。
具体来说在有序区和无序区各需要两个指针。有序区的两个指针：p用来遍历已排序部分，用于找到比 q->data 大或相等的节点，即插入位置；辅助指针s，指向 p 的前驱节点，用于在找到插入位置后，调整指针完成插入操作。无序区的两个指针：q为当前正在进行插入排序的节点（待插入的结点）；t用来暂存 q 的下一个节点，保证在当前节点 q插入完后，能够继续遍历链表。
Linklist sort_list(Linklist &L){
if (!L || !L->next || !L->next->next) return L;
Lnode *p,*q,*s;
p=L->next;
q=p->next;
p->next=NULL; // 分割有序区和无序区
while(q){
Lnode *t=q->next;
s=L;
p=L->next;
while (p && p->data < q->data) { // 寻找插入位置
s = p;
p = p->next;
}
q->next = p;
s->next=q;
q=t;
}
return L;
}
实践：
完整代码如下：
#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_list(Linklist &L){if (!L || !L->next || !L->next->next) return L; Lnode *p,*q,*s;p=L->next;q=p->next;p->next=NULL;while(q){Lnode *t=q->next;s=L;p=L->next;while (p && p->data < q->data) {s = p;p = p->next;}q->next = p;s->next=q;q=t;}return L;
}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");sort_list(L);printf("new list:");Lnode *q = L->next;while (q != NULL) {printf("%d-> ",q->data);q = q->next;}printf("NULL");return 0;
}
