单链表的常见题型汇总(二)
109@gmail.com
> Created Time: 2014年05月19日 星期一 12时44分36秒
************************************************************************/
#include
#include
typedef struct Node { int elem ; Node *Next ; }List; void InitList(List *L) ; void Insert(int e,List *L) ; void Delete(int e,List *L) ; void PrintList(List L) ; /* 链表反转 */ void ReverseList(List *L) ; /* 求单链表倒数第N个数 */ int NIndex(List L,int n) ; /* 输出单链表的中间结点*/ int Mid(List L) ; /*判断链表是否存在环 */ bool HasCycle(List *L) ; /* 如果单链表没环，则给它制指定位置n建环操作 */ void CreateCycle(int n,List *L) ; /* 如果存在环，则输出其长度*/ int LenCycle(List *L) ; /* 输出环的链接点*/ int EntryCycle(List *L) ; /* 删除相同的元素*/ void DelSame(List *L) ; main() { List L ; InitList(&L) ; Insert(1,&L) ; Insert(2,&L) ; Insert(3,&L) ; Insert(2,&L) ; Insert(5,&L) ; //Delete(1,&L); DelSame(&L) ; PrintList(L) ; printf("\n") ; ReverseList(&L) ; PrintList(L) ; printf("\n") ; printf("%d\n",NIndex(L,2)) ; printf("%d\n",Mid(L)) ; if(HasCycle(&L)) printf("L has cycle!\n") ; else printf("L hasn't cycle\n") ; CreateCycle(2,&L) ; if(HasCycle(&L)) printf("L has cycle!\n") ; else printf("L hasn't cycle\n") ; //CreateCycle(1,&L) ; //会提示已经有环了，不能再创建 printf("the length cycle is %d\n",LenCycle(&L)) ; printf("the entry is %d\n",EntryCycle(&L)) ; } /* 链表反转 */ void ReverseList(List *L) { if(!L->Next->Next) ; else{ List *pTemp = L->Next->Next->Next ; List *pMid = L->Next->Next ; List *pCurrent = L->Next ; L->Next->Next = NULL ; while(pTemp){ pMid->Next = pCurrent ; pCurrent = pMid ; pMid = pTemp ; pTemp = pTemp->Next ; } pMid->Next = pCurrent ; L->Next = pMid ; } } /* 求单链表倒数第N个数 */ int NIndex(List L,int n) { List *fir,*sec ; fir = L.Next ; sec = L.Next ; int i ; for(i=0;sec;++i){ if(i>=n){ fir = fir->Next ; sec = sec->Next ; }else sec = sec->Next ; } return fir->elem ; } /* 输出单链表的中间结点*/ int Mid(List L) { List *fir,*sec ; fir = L.Next ; sec = L.Next ; while(sec->
Next&&sec->Next->Next){ fir = fir->Next ; sec = sec->Next->Next ; } return fir->elem ; } /*判断链表是否存在环 */ bool HasCycle(List *L) { List *slow,*fast ; /* 一个走两步，一个走一步*/ slow = L ; fast = L ; while(fast&&fast->Next){ slow = slow->Next ; fast = fast->Next->Next ; if(slow == fast) break ; } return !(fast==NULL||fast->Next == NULL) ; } /* 如果单链表没环，则给它制指定位置n建环操作 */ void CreateCycle(int n,List *L) { if(HasCycle(L)){ printf("L has already cycle!") ; exit(-1) ; } List *entry,*pCurrent ; //环入口结点 int i ; pCurrent = L ; for(i=0;pCurrent->Next;++i){ if(i==n) entry = pCurrent ; pCurrent = pCurrent->Next ; } if(i
Next = entry ; } /* 如果存在环，则输出其长度*/ int LenCycle(List *L) { int i,k ; i=k=0 ; if(HasCycle(L)){ List *slow,*fast ; slow = L ; fast = L->Next->Next ; while(i!=2){ if(i==1) ++k ; if(slow==fast){ ++i ; } slow = slow->Next ; fast = fast->Next->Next ; } }else{ printf("L hasn't cycle!\n") ; exit(-1) ; } return k ; } /* 输出环的链接点*/ int EntryCycle(List *L) { if(HasCycle(L)){ List *slow,*fast ; /* 一个走两步，一个走一步*/ slow = L ; fast = L ; while(fast&&fast->Next){ slow = slow->Next ; fast = fast->Next->Next ; if(slow==fast) break ; } List *head = L ; while(head!=slow){ head = head->Next ; slow = slow->Next ; } return slow->elem ; }else{ printf("L hasn't cycle!") ; } } /* 删除相同的元素*/ void DelSame(List *L) { List *run,*pCurrent ; pCurrent = L->Next ; while(pCurrent){ run = pCurrent->Next ; while(run){ printf("hello\n") ; if(pCurrent->elem == run->elem){ printf("world\n") ; Delete(pCurrent->elem,L) ; break ; } run = run->Next ; } pCurrent = pCurrent->Next ; } } /* 链式存储链表的基本操作*/ void InitList(List *L) { L->Next = NULL ; } void Insert(int e,List *L) { List *pCurrent ; pCurrent = L ; List *eNode = (List*)