单链表操作（一）

将一个带有头结点的单链表反向输出

思想：每当访问一个结点时，先递归输出它后面的结点

void ReverseList(LinkList &L){ if(L->next!=NULL){ ReverseList(L->next); } printf("%d ",L->data);}

函数调用为：ReverseList(L->next);不能从头结点开始，不然也会输出头结点的的值

 

将一个链表（a1,b1,a2,b2,,,,an,bn）拆为两个链表(a1,a2,a3,,,an),(b1,b2,b3,,,bn);

 

void Discrate1(LinkList &L){ int i=0; LinkList p,r,s; p=L->next; CreatList(r); CreatList(s); while(p!=NULL){ if(i%2==0){ ListTailInsert(r,p->data); } else{ListTailInsert(s,p->data);} i++; p=p->next; } ListPrint(r); ListPrint(s);}

 

在一个递增的单链表中删除相同的元素

void DisCrate2(LinkList &L){ LinkList p; p=L->next; while(p!=NULL){if(p->next==NULL){break;}//一定要加入判断是否为最后一个结点，不然下一句会引起报错。 if(p->data==p->next->data){ p->next=p->next->next; } p=p->next; }}

 

返回一个有头结点的链表倒数第k个结点的值

思想：因为是高效的算法要求一遍扫描就能得出结果，所以可以设置两个指针p,q同时指向头结点，p指针首先沿着链表移动k个结点，然后q和p同时移动，当p指针指向最后一个结点时，q恰好指向了倒数第k个结点。

我开始是直接递归到最后一个结点然后返回找倒数第k个结点，但是这貌似不高效

int ReverseCount(LinkList &L,int k){ LinkList r,p; p=L->next; r=L->next; int count; for(count=0;count<k;count++){ p=p->next; } while(p!=NULL){ r=r->next; p=p->next; } if(count==k){printf("%d\n",r->data);return 1;} else return 0;}

 

找出个链表存在相同结点的初始位置

思想：两条链表若有相同的结点，那么并呈现出"Y"状，而不可能是"X"状

void SerchList(LinkList &L1,LinkList &L2){ LinkList p1=L1->next; LinkList p2=L2->next; int j=0; int diff;//两个链表的长度的差值 if(L1->length>L2->length){ diff=L1->length-L2->length;; for(int i=0;i<diff;i++){ p1=p1->next; } } else{ diff=L1->length-L2->length; for(int i=0;i<diff;i++){ p2=p2->next; } } while(p1!=NULL){ if(p1->data==p2->data){ printf("位于较长结点的第%d位\n",j+diff); break; } p1=p1->next; p2=p2->next; j++; }}

void ListLink(LinkList &L1,LinkList &L2){ LinkList p1; p1=L1->next; LinkList p2; p2=L2->next; while(p1->next!=NULL){ p1=p1->next; } p1->next=p2;}//将一个链表与另一个链表末尾连接起来

转载于:https://www.cnblogs.com/Yshun/p/11141045.html

相关资源：实验报告2 单链表的操作