1.递归删除所有值为x的节点
void Del_X(LinkList &L,int x){
if(L == null) return; //递归出口
if(L->next != x){
Del_X(L->next,x); //若L指的节点不为x，那么就继续向后走
return;
}
LNode *p; //创建指向要删除的节点
p = L; //p指向本层节点
L = L->next;
delete(p);
Del_X(L->next,x); //递归调用
}
2.删除所有值为x的节点(没要求递归)
思路：创建一个p和pre指针，一个指向当前节点，一个指向前一个节点
如果遇到相同，那么就"跨越"这个节点
void Del_X(LinkList &L,int x){
LNode *p=L->next,*pre=L,*q; //初始p和pre
while(p != NULL){
if(p->data == x){
q = p; //q指向p
p = p->next; //p继续向前走
pre->next = p;
/*
pre指向p 从而跨越了中间的节点，实现删除的效果
*/
delete q;
}else{
pre = p; // 正常往前走
p = p->next;
}
}
}
3.反向输出链表
思路：一直递归到最后，从而输出从里层往外输出
void Rever(LinkList &L){
if(L->next != NULL){
Rever(L->next); //一直递归到最后
}
cout << L->data;
}
4.删除链表中最小元素
思路:维护最小值指针和他的前驱指针，遍历记录最小值，最后删除
void DeleMin(LinkList &L){
LNode *pre=L,*p=pre->next;
LNode *minpre=pre,*minp=p; //记录最小值得节点以及他的前驱
while(p != NULL){
if(p->data < minpre->data){ //后一个比前一个小
min = p; //维护min处于最小节点位置
minpre = pre; //维护minpre处于最小节点的前驱
}
p = p->next; //大步往前走
pre = pre->next; //大步往前走
}
minpre->next = min->next; //删除最小值
free(minp);
return L;
}
5.链表就地反转
思路：维护两个指针，cur和pre，让pre永远在cur的前方
ListNode reverseList(ListNode head) {
ListNode *cur = NULL, *pre = head;
while (pre != NULL) {
ListNode *t = pre->next; //再存pre的下一个指针
pre->next = cur; //pre指向cur
cur = pre; //cur往前走一步
pre = t; //pre往前走一步
}
return cur;
}
6.重排链表，使其变成递增序列
思路：使用插入排序每次遍历到的节点，插入到前面的有序表中
void Sort(LinkList &L){
LNode *p = L->next;
LNode *r = p->next; //保存p的后继，防止断链
LNode *pre;
p->next = NULL; //构造第一个有序表
p = r;
while(p != NULL){
r = p->next;
pre = L;
while(pre->next != NULL && pre->next->data < p->data){
pre = pre->next; //pre往前走，寻找插入p的前驱结点
}
p->next = pre->next; //将*p插入到*pre之后
pre->next = p;
p = r;
}
}
7.删除介于两个值之间的所有节点(类似上一篇的线性表有道题)
思路：维护一个节点的前驱指针，要删除的时候使用前驱指针
void RangeDel(LinkList &L,int min,int max){
LNode *pr = L;
LNode *p = L->next;
while(p != NULL){
if(p->data > min && p->data < max){
pr->next = p->next; //跨越这个节点，准备卸磨杀驴
free(p);
p = pr->next; //p继续向前走
}else{
pr = p;
p = p->next;
}
}
}
8.寻找两个链表的公共结点
思路：先让腿长的人先跑前面的差程，然后和腿短的人一起跑，一起寻找交叉点
LinkList SearchList(LinkList L1,LinkList L2){
int len1 = Length(L1);
int len2 = Length(L2);
int dist;
LinkList longLis,shortList; //指向较长和较短的链表
if(len1 > len2){ //L1长
longLis = L1->next;
shortList = L2->next;
dist = len1 - len2;
}else{
longLis = L2->next;
shortList = L1->next;
dist = len2 - len1;
}
while(dist--){
longLis = longLis->next; //先让腿长的先跑
}
while(longLis != NULL){
if(longLis == shortList) return longLis;
else{ //寻找那个同时跑的 起跑线
longLis = longLis->next;
shortList = shortList->next;
}
}
return NULL;
}
9.升序输出链表
思路：每次找m最小值，从而输出再释放结点
void SortPrint(LinkList &head){
while(head->next != NULL){
pre = head; //必须维护一个前驱指针
p = pre->next; //p是当前遍历指针
while(p->next != NULL){
if(p->next->data < pre->next->data){
pre = p; //标记p(最小值)的前驱位置
p = p->next;
}
print(pre->next->data);
w = pre->next; //释放这个替死鬼
pre->next = w->next;
free(w);
}
free(head);
}
}
10.将题中链表分为序号奇偶两个链表
思路：设两个指针分别指向新的两个链表
LinkList DisCreat(LinkList &A){
int i = 0;
B = (LinkList)malloc(sizeof(LNode));
B->next = NULL; //B表初始化
LNode *ra = A,*rb = B; //分别指向AB两表
p = A->next; //p为工作指针
A->next = NULL;
while(p != NULL){
i++;
if(i&2 == 0){ //序号为偶
rb->next = p; //插入rb表
rb = p; //指向新的尾节点
}else{ //序号为奇
ra->next = p;
ra = p;
}
p = p->next; //p 往前走
}
ra->next = NULL;
rb->next = NULL;
return B;
}
11.将{a,b,a,b...}拆成{a,a,a..},{b,b,b...}
思路：与10题思路一样，只不过改成头插法(题目要求)
LinkList DisCreat_2(LinkList &A){
LinkList B = (LinkList)malloc(sizeof(LNode));
B->next = NULL;
LNode *p = A->next,*q;
LNode *ra = A; //ra始终指向A的尾部
while(p != NULL){
ra->next = p;
ra = p; //将指向A的尾部
p = p->next;
if(p != null) q = p->next; //用q保存p的后继，否则会断链
p->next = B->next; //头插到B的后面
B->next = p;
p = q;
}
ra->next = NULL; //A的尾部置空
return B;
}
12.删除递增表的重复元素
思路：工作指针和后继节点相同时则删除
LinkList DelSame(LinkList &L){
LNode *p = L->next,*q; //p为工作指针
if(p == NULL) return;
while(p->next != NULL){
q = p->next; //q始终为p的后继节点
if(p->data == q->data){
p->next = q->next;
free(q);
}else{
p = p->next;
}
}
}
13.将两个递增链表合并为一个递减链表
思路：同时移动两个指针将较小元素节点的存入链表
LinkList MergeList(LinkList &La,LinkList &Lb){
LNode *r,*pa=La->next,*pb=Lb->next; //分别指向两个链表
La->next = NULL; //La作为结果链表的头指针
while(pa && pb){
if(pa->data <= pb->data){
r = pa->next;
pa->next = La->next;
La->next = pa; //头插逆置 为了维护递减
pa = r; //恢复pa的位置
}else{
r = pa->next;
pb->next = La->next;
La->next = pb; //头插逆置 为了维护递减
pb = r; //恢复pb的位置
}
if(pa){
pb = pa; //处理非空链表
}
while(pb){ //依次头插到La中
r = pb->next;
pb->next = La->next;
La->next = pb;
pb = r;
}
free(Lb);
}
}
14.A、B为递增链表，找到公共部分，产生C链表
思路：两个指针一起走，谁小谁先走，找到公共节点再继续走
LinkList GetComm(LinkList A,LinkList B){
LNode *p=A->next,*q=B->next,*r,*s //分别指向两个链表
LinkList C = (LinkList)malloc(sizeof(LNode));
r = c; //r始终指向c的尾巴
while(p!=NULL && q!+NULL){ //谁小 谁先走
if(p->data < p->data){
p = p->next;
}else if(p->data > p->data){
q = q->next;
}else{
s = (LNode*)malloc(sizeof(LNode));
s->data = p->data; //复制p数值
r->next = s; //尾插到C上
r = s;
p = p->next; //继续走
q = q->next;
}
r->next = NULL;
}
15.找两个递增的链表的交集
思路：二路归并(此题考的几率巨大，书上说的...)
LinkList GetComm(LinkList &la,LinkList &lb){
LNode *pa=la->next,pb=lb->next; //分别指向两个链表
pc = la; //pc一直指向la
while(pa && pb){ //谁小 谁先走
if(p->data == p->data){
pc->next = pa;
pc = pa;
pa = pa->next;
u = pb; //替死鬼
pb = pb->next;
free(u);
}else if(pa->data < p->data){
u = pa;
pa = pa->next;
free(u)
}else{
u = pb;
pb = pb->next;
free(u)
}
while(pa){
u = pa;
pa = pa->next;
free(u)
}
while(pb){
u = pb;
pb = pb->next;
free(u)
}
free(lb);
pc->next = NULL; //老套路，把新表的路封死
}
16.判断序列B是不是A的子序列
思路：B一直重复，A一直往前走，用来找公共的节点
int Pattern(LinkList A,LinkList B){
LNode *p = A; //p是A的工作指针
LNode *pre = A; //记住每次比较中A链表开始的节点
LNode *q = B;
while(p && q){
if(p->data == q->data){ //节点相同时
p = p->next;
q = p->next;
}else{
pre = pre->next;
p = pre; //A新的开始
q = B; //B重复
}
if(q == NULL){
return 1;
}else{
return 0;
}
}
17.判断是否是 回文链表
思路：两边来回判断
int Symmetry(DLinkList L){
DNode *p = L->next; //p是L的往后的工作指针
DNode *q = L->prior; //q是L的往前的工作指针
while(q!=q &&p->next!=q){ //节点数为奇或偶的时候
if(p->data == q->data){ //节点相同时
p = p->next; //往后走
q = p->prior; //往前走
}else{
return 0 //比较失败
}
}
return 1;
}
18.将A链接到B链表上，使之仍然为循环链表
思路：将B链接到A的尾巴上面
LinkList Link(LinkList &h1,LinkList &h2){
LNode *p,*q;
p = h1;
while(p->next != h1){ //寻找h1的尾节点
p = p->next;
}
q = h2;
while(q->next != h2){ //寻找h2的尾节点
q = q->next;
}
p->next = h2; //h2链接到h1之后
q->next = h1; //h2的尾巴指向h1
return h1;
}
19.循环单链表，每次输出并删除最小值节点
思路：每次循环记录最小值的位置，然后进行删除操作
LinkList Link(LinkList &L){
LNode *p,*pre,*minp,*minpre;
while(L->next != L){
p = L->next; //L为工作指针
pre = L; //pre为p的前驱指针
minp = p; //记录最小值的位置
minpre = pre;
while(p != L){
if(p->data < minp->data){ //一直找最小的值
minp = p;
minpre = pre;
}
pre = p;
p = p->next;
}
print("%d",minp->data); //输出最小值节点元素
minpre->next = minp->next; //删除最小值
free(L);
}
}
21.高效的寻找倒数第K个节点
思路：设置两个指针，先让p走k步，再p和q一起走，p走到最后，q就是要求的值
int serch(LinkList list,int k){
LNode *p,=list->link,*q=list->link;
int count = 0;
while(p != NULL){
if(count < k){
count++; //前k步先让p先走
}else{
q = q->link;
}
p = p->link;
}
if(count < k)return 0; //失败
else{
printf("%d",p->data);
return 1;
}
}
22.找公共节点，并返回公共节点的地址
思路：与前面的题重复，这里就不做过多赘述
typedef struct Node{
char data;
struct Node *next;
}
int Len(SNode *head){
int len = 0;
while(head->next != NULL){
len++;
head = head->next;
}
return len;
}
SNode* findAddr(SNode *str1,SNode *str2){
int m n;
SNode *p,*q;
m = Len(str1);
n = Len(str2);
for(p=str1;m>n; m--){ //假设m>n，那就先让p先走
p = p->next;
}
for(q=str1;m<n; n--){ //假设m>n，那就先让p先走
q = q->next;
}
while(p->next!=NULL && p->next!=q->next){
p = p->next;
q = q->next;
}
return p->next;
}
23.保留第一次出现的节点，删除其他绝对值相等的节点
思路：题目中给出时间的限制，所以直接空间换时间，使用数组标记
void func(Pnode h,int n){
Pnode p = h,r;
int *q,m;
q = (int *)malloc(sizeof(int )*(n+1)); //开辟n+1个空间
for(int i=0; i<n+1; i++){
q[i] = 0;
}
while(p->link != NULL){
//保证m是正数
m = p->link->data>0? p->link-data : -p->link->data;
if(q[m] == 0){
q[m] = 1; //首次出现,置为1
p = p->next;
}else{
r = p->link; //替死鬼
p->link = r->link; //跨越式删除
free(r);
}
}
free(q);
}
24.判断链表是否有环，如果有则输出换的入口地址
思路：使用快慢指针，slow走一步，fast走两步，(证明自行看书)
Lnode* FindLoop(Lnode *head){
Lnode *fast = head,*slow = head;
while(slow!=NULL && fast!=NULL){
slow = slow->next; //走一步
fast = fast->next->next; //走两步
}
if(slow==NULL || fast==NULL){
return NULL;
}
Lnode *p1=head,*p2=slow;
while(p1 != p2){
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
25.
将前面序列变为后面序列
思路：先找中间节点，将后半段序列逆置，从而后面取一个前面取一个
void change(node *h){
node *p,*q,*r,*s;
q = p = h;
while(q->next != NULL){ //找中间节点
p = p->next;
q = q->next;
if(q->next != NULL)
q = q->next; //走两步
}
q = p->next; //p指向中间节点
p->next = NULL;
while(q != NULL){ //后半段逆置
r = q->next;
q->next = p->next;
p->next = q;
q = r;
}
s = h->next;
q = p->next;
p->next = NULL;
while(q != NULL){ //将链表后半段的节点插入到指定位置
r = q->next; //r指向后半段的下一个节点
q->next = s->next; //将其所指节点插入到s后面
s->next = q; //s指向前半段的下一个插入点
s = q->next;
q = r;
}
}
链表完美撒花
