reverse a singly linked list扭转单链表

《reverse a singly linked list扭转单链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C/C++Interviewalgorithms1.DataStructure1.1.LinkedList1.1.1.ReverseasinglylinkedlisttypedefstructtagNODE{intiData;tagNODE*prNext;}NODE,*PNODE;//iterativeversionvoidReverseList(PNODE*pprHead){PNODEprHead;PNODEprTail;prHead=*pprHead;prTail=NULL;//while(prHead){PNODEprSave;//Savethe"next"nodeinth

2、elistprSave=prHead->prNext;//PointthecurrentnodeatthepreviousnodeprHead->prNext=prTail;//ThiswillbecomethepreviousnodeforthenextiterationprTail=prHead;//AdvancethecurrentnodeforthenextiterationprHead=prSave;}//Updatethenewheadpointer*pprHead=prTail;}1.1.2.Reversethepairsofelementsinasigledlin

3、kedlistvoidReverseListPair(PNODE*pprHead){PNODEptrPairPre=null;//1(head)->2----à3PNODEptrPairCurr=(*pprHead)->prNext;if(null==ptrPairCurr)return;//1(head)---->3(*pprHead)->prNext=ptrPairCurr->prNext;//2->(1)headptrPairCurr->prNext=*pprHead;//head=2:2(head)->1---à3*pprHead=ptrPairCurr;//2(head

4、)->1(pairPre)---à3ptrPairPre=ptrPairCurr->prNext;Page14of14C/C++Interviewalgorithms//2->1(pairPre)à3->4while(ptrPairPre->prNext&&ptrPairPre->prNext->prNext){//2->1(pairPre)à3->4(pairCurr)---à5ptrPairCurr=ptrPairPre->prNext->prNext;//2->1(pairPre)à3----->5ptrPairPre->prNext->prNext=ptrPairCurr

5、->ptrNext;//4(pairCurr)->3ptrPairCurr->ptrNext=ptrPairPre->prNext;//1(pairPre)à4(pairCurr)ptrPairPre->prNext=ptrPairCurr;//2->1à4->3(pairPre)---à5ptrPairPre=ptrPairCurr->prNext;}1.1.1.DeleteanodeindoublelinkedlistvoiddeleteNode(node*n){node*np=n->prev;node*nn=n->next;np->next=n->next;nn->prev

6、=n->prev;deleten;}1.1.2.Sortalinkedlist//sortingindescendingorderstructnode{intvalue;node*NEXT;}//AssumeHEADpointerdenotesthefirstelementinthelinkedlist//onlychangethevalues…don’thavetochangethepointers//thefollowingusesselectionsort,inwhichthe1stminimum,2ndminimum…//arefoundandmovetothefinal

7、positionsubsequentlySort(Node*Head){node*first,second,temp;first=Head;while(first!=null){second=first->NEXT;while(second!=null){if(first->valuevalue){temp=newnode();temp->value=first->value;first->value=second->value;second->value=te