1.设计一个递归算法，删除不带头节点的单链表L中所有值为x的节点
算法思想：先递归到最后一个结点，从后向前判断各结点值是否等于x，若等于，返回当前结点的下一个结点的指针给上一个节点的指针，否则返回自己
typedef struct ListNode{
ElemType val;
struct ListNode* next
}ListNode,*LinkList;
LinkList Delete_x(LinkList L,ElemType x){
if(!L){ //递归出口
return NULL;
}
L->next = Delete_x(L->next,x);//向后递归至最后一个节点
return L->val == x? L->next;L;//节点值是否等于x，若相等返回下一个节点指针到上一层
}
2.在带头结点的单链表L中，删除所有值为x的节点，并释放空间，假设值为x的节点不唯一
①迭代法
方式一：遍历指针cur始终指向待判断节点的上一个节点，pre保存待删除结点指针，cur指向待删除结点的前驱结点，便于删除结点，不断链
方式二：遍历指针cur始终指向待判断结点，pre指向cur的前驱结点，用pre来删除待删除结点，会断链
typedef struct ListNode{
ElemType val;
struct ListNode* next
}ListNode,*LinkList;
//方式一
void Delete_x(LinkList L,ElemType x){
LinkList cur = L,pre = NULL;//pre保存待删除结点指针
while(cur->next){
if(cur->next->val == x){
pre = cur->next;
cur->next = cur->next->next;
free(pre);
}else{
cur = cur->next;
}
}
}
//方式二
void Delete_X(LinkList L,ElemType x){
LinkList cur = L->next,pre = L;
while(cur){
if(cur->val == x){
pre->next = cur->next;
free(cur);
cur = pre->next;
}else{
pre = cur;
cur = cur->next;
}
}
}②尾插法建立单链表法
算法思想：遍历链表，将值不等于x的结点逐个尾插到头节点后
void Delete_x(LinkList L,ElemType x){
LinKList rear = L;//尾指针
LinkList p = L->next,q;
while(p){
if(p->val != x){
rear->next = p;
rear = p;
p = p->next;
}else{
q = p;
p = p->next;
free(q);
}
}
rear->next = NULL;
}3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个节点的值
①递归
算法思想：从链表第一个结点开始递归至链表最后第一个结点，递归返回时将结点值逐个输出
void L_Print(LinkList L){
if(L == NULL){//递归出口
return;
}
L_Print(L->next);
print(L->val);
}
void L_Print_Head(LinkList L){
if(L){
L_Print(L->next);
}
}
②迭代法
算法思想：将链表反向链接，再遍历输出节点值
void revese_print(LinkList L){
LinkList cur = L->next;//遍历指针
LinkList pre = NULL;//指向cur的上一个结点
LinkList temp；//保存cur的下一个结点，防止断链
while(cur){
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
L->next = pre;
while(L->next){
print(L->next->val);
L = L->next;
}
}4.试编写在带头结点的单链表L中删除一个最小值节点的高效算法假设最小值节点是唯一的
算法思想：遍历链表，寻找最小结点，保存最小结点和其前驱的指针，以便删除
void DeleteminValue(LinkList L){
LinkList p = L->next,pre = L;
LinkList minp = L->next,minpre = L;
while(p){
if(p->val < minp->val){
minp = p;
minpre = pre;
}else{
pre = p;
p = p->next;
}
}
minpre->next = minp->next;
free(minp);
}5.逆置(反转)链表:头插、迭代、递归，同上
6.有一个带头结点的单链表L，设计一个算法使其递增有序
算法思想：用直接插入排序的思想，将链表第一个结点归为有序，依次遍历链表其他结点，寻找插入位置，并将其插入使其链表有序
void Sort(LinkList L){
if(L == NULL && L->next == NULL){//若链表为空
return;
}
LinkList p = L->next;
LinkList r = p->next;//保存无序序列的第一个结点，以防断链
p->next = NULL;
r = p;//p始终指向无序序列的第一个结点
LinkList pre;
while(p){
r = p->next;
pre = L;//pre指向有序链表
//寻找插入位置
while(pre->next && pre->next->val < p->val){
pre = pre->next;
}
//将待插入结点插入
p->next = pre->next;
pre->next = p;
r = p;//遍历无序序列的下一个结点
}
}7.设在一个带表头结点的单链表中所有元素节点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值(作为函数参数给出)之间的元素(若存在)
迭代法 ①方式一 ②方式二 同第2题
//方式一
void Delete_Range(LinkList L,ElemType max,ElemType min){
LinkList cur = L,pre;
while(cur->next){
if(cur->next->val > min && cur->next->val < max){
pre = cur->next;
cur->next = cur->next->next;
free(pre);
}else{
cur = cur->next;
}
}
}
//方式二
void Delete_Range(LinkList L,ElemType max,ElemType min){
LinkList cur = L->next,pre = L;
while(cur){
if(cur->val < max && cur->val > min){
pre->next = cur->next;
free(cur);
cur = pre->next;
}else{
pre = cur;
cur = cur->next;
}
}
}8.给定两个单链表，编写算法找出两个链表的公共节点：找到第一公共节点等于所有公共节点全部找到
①长度作差同步遍历
算法思想：遍历两个链表，将较长的链表先遍历两个链表差值次使其两个链表此时的长度相同，再同步遍历两个链表，在遍历过程中若两个指针相同，此时该指针指向的结点就是两个链表的公共结点
int Get_Length(LinkList L){
int count = 0;
while(L){
count++;
L = L->next;
}
return count;
}
LinkList Common_Node(LinkList L1,LinkList L2){//假设L1,L2不带头结点
int len1 = Get_Length(L1),len2 = Get_Length(L2);
int distance;//记录长度差值
LinkList shortList,longList;//记录较长和较短链表的头指针
if(len1 > len2){//L1为较长链表
longList = L1;
shortList = L2;
distance = len1 - len2;
}else{
longList = L2;
shortList = L1;
distance = len2 - len1;
}
//同步两个链表
while(distance--){
longList = longList->next;
}
//同步遍历
while(longList){
if(longList == shortList){
return longList;
}else{
longList = longList->next;
shortList - shortList->next;
}
}
return NULL;//无公共结点
}②双指针交替遍历
算法思想：用双指针分别遍历两个链表，其中一个指针遍历完较短链表后再从头遍历另一个较长链表，待到另一个指针遍历较长链表后，要遍历较短链表时，此时两个链表后面的长度相同，再同步遍历两个链表，同上
LinkList Commom_Node(LinkList L1,LinkList L2){
if(L1 == NULL || L2 == NULL){
return;
` }
LinkList cur1 = L1,cur2 = L2;
while(cur1 != cur2){
cur1 = cur1 == NULL? L2 : cur1->next;
cur2 = cur2 == NULL? L1 : cur2->next;
}
return cur1;//cur1可能是公共结点，也可能是NULL
}9.给定一个带表头节点的单链表L，写出算法：按递增次序输出单链表中各节点的值，并释放其空间
算法思想：每次从当前链表中选取最小的结点输出并释放空间，直至链表为空
void Print_min(LinkList L){
//pre始终指向最小结点的前驱结点，以便删除，p为遍历指针，寻找最小结点
LinkList p,pre;
while(L->next){//循环至只剩头节点
p = L->next;//假设当前链表的第一个结点为最小结点,p初始时指向
pre = L;
//寻找当前链表的最小结点
while(p->next){
if(p->next->val < pre->next->val){
pre = p;//让pre指向该最小结点的前驱结点
}
p = p->next;
}
print(pre->next->val);//输出其结点值
//删除该最小结点
LinkList temp = pre->next;
pre->next = temp->next'
free(temp);
}
free(L);//释放头节点
}10.将一个带头节点的单链表A分解为两个带头结点的单链表A和B，使得A中含原链表中序号为奇数的元素，B中含原链表中序号为偶数的元素，并且保持相对顺序不改变
算法思想:遍历链表，用尾插法分别将奇数和偶数序号对应的结点插入对应的链表中
LinkList SetPart(LinkList A){
LinkList B = (LinkList)malloc(sizeof(ListNode));
B->next = NULL;//创建B链表头节点
LinkList rB = B;//B链表尾指针
LinkList cur = A->next;
A->next = NULL;
LinkList rA = A;//A链表尾指针
while(cur){
rA->next = cur;
rA = cur;
cur = cur->next;
if(cur){
rB->next = cur;
rB = cur;
cur = cur->next;
}
}
rA->next = NULL;
rB->next = NULL;
return B;
}11.设A={a1,b1,a2,b2,...,an,bn}为带头节点的单链表,将其分解为两个单链表A,B，其中A={a1,a2...,an},B={bn,.....b2,b1}
算法思想：类似于第10题，不同的是对B用头插法使偶数序号的结点顺序颠倒
LinkList SetPart(LinkList A){
LinkList B = (LinkList)malloc(sizeof(ListNode));
B->next = NULL;//创建B链表头节点
LinkList cur = A->next;
A->next = NULL;
LinkList rA = A;//A链表尾指针
LinkList temp;//对B用头插时，保存cur的下一个结点，以防断链
while(cur){
rA->next = cur;
rA = cur;
cur = cur->next;
if(cur){
//进行头插
temp = cur->next;
cur->next = B->next;
B->next = cur;
B = temp;
}
}
rA->next = NULL;
return B;
}
12.在递增有序的单链表中，移除重复的元素，使元素唯一
算法思想：由于链表递增有序，重复的元素位置必定连续，遍历链表，若指针指向的结点值和下一个结点值若相同，删除后者，若不同，遍历下一个结点
void Del_SameNode(LinkList L){
if(!L->next){
return NULL;
}
LinkList cur = L->next;
LinkList temp；//保存待删除结点的指针
while(cur->next){//判断cur的下一个结点是否为空
if(cur->val == cur->next->val){
temp = cur->next;
cur->next = cur->next->next;
free(temp);
}else{
cur = cur->next;
}
}
}