1、寻找一个单向链表的倒数第n个节点;
2、二分查找以及二分查找寻找上下界;
3、求交叉链表的第一个交叉节点;
#include <assert.h> #include <stdio.h> #include <stdlib.h> using namespace std ; struct _link_node{ int data ; struct _link_node *next ; } ; struct _link_node* create_linklist(int data[],int len){ assert(data!=NULL) ; struct _link_node *pRoot = (struct _link_node*)malloc(sizeof(struct _link_node)) ; //pRoot->next = NULL ; struct _link_node *pTmp = pRoot ; for(int i=0;i<len;i++){ pTmp->next=(struct _link_node*)malloc(sizeof(struct _link_node)) ; pTmp->next->data = data[i] ; pTmp = pTmp->next ; } pTmp->next = NULL ; return pRoot ; } struct _link_node* print_link(struct _link_node* pRoot){ struct _link_node *pTmp = pRoot ; while(pTmp->next!=NULL){ printf("%d,",pTmp->next->data) ; pTmp=pTmp->next ; } } struct _link_node* get_reverse_n(struct _link_node* pRoot,int n){ assert(pRoot!=NULL) ; struct _link_node *pPre = pRoot ; struct _link_node *pTail = pRoot ; int cnt = 0 ; /*使用两个指针,第一个指针比第一个指针先走n步,两个指针再一起移动, 当先走指针走向末尾时,另外一个指针所指向的位置就是倒数第n个*/ while(cnt<n){ if(pPre==NULL){ return NULL ; } cnt++ ; pPre=pPre->next ; } while(pPre!=NULL&&pPre->next!=NULL){ pPre=pPre->next ; pTail=pTail->next ; } return pTail->next ; } void PrintMeet(){ int hour=0 ; int minutes=0 ; for(int i=1;i<6;i++){//模拟时针每走一小时,角度是30度 hour+=30 ; for(int j=0;j<60;j++){//模拟秒针走,一步角度为6; minutes+=6 ; if(minutes%360==hour){ printf("time=%d:%d\n",hour/30,minutes%360/6) ; } } } } int binary_search(int array[],int low,int high,int target){ if(low>high||array[high]<target){//advance abort return -1 ; } int mid = low+((high-low)>>1) ; while(low<=high){ mid = low+((high-low)>>1) ; if(array[mid]<target){ low = mid+1 ; }else if(array[mid]>target){ high = mid-1 ; }else{ return mid ; } } return -1 ; } int binary_search1(int array[],int low,int high,int target){ if(low>high){ return -1 ; }else{ int mid = low+((high-low)>>1) ; if(array[mid]>target){ high = mid-1 ; binary_search1(array,low,high,target) ; }else if(array[mid]<target){ low = mid + 1 ; binary_search1(array,low,high,target) ; }else{ return mid ; } } } int binary_find_upper_bound(int array[],int low,int high,int target){ if(low>high||array[high]<target){//advance abort return -1 ; } int mid =low + ((high-low)>>1) ; while(low<high){ if(array[mid]>target){ high = mid ; }else{ low = mid+1 ; } mid = low+((high-low)>>1) ; } return array[mid] ; } int binary_find_lower_bound(int array[],int low,int high,int target){ if(low>high||array[high]<target){//advance abort return -1 ; } int mid = low+((high-low)>>1) ; while(low<high){ if(array[mid]<target){ low = mid ; }else{ high=mid-1 ; } mid = low + ((high-low+1)>>1) ;//note:here we must add 1 to compute mid } return array[mid] ; } int find_first_cross_node(struct _link_node*pFirst, struct _link_node *pSecond){ assert(pFirst!=NULL&&pSecond!=NULL) ; int len_first=0 ; int len_second=0 ; struct _link_node *pTmp1=pFirst ; struct _link_node *pTmp2=pSecond ; //first compute length of the two link list while(pTmp1->next!=NULL){ pTmp1=pTmp1->next ; len_first++ ; } while(pTmp2->next!=NULL){ pTmp2=pTmp2->next ; len_second++ ; } // if not have cross ,return -1 if(pTmp1!=pTmp2){//if not cross return -1 ; } //compare length of the two link list and difference of two link list length, //and decide which list should move first int b_first_long=len_first>len_second ; int diff=b_first_long?(len_first-len_second):(len_second-len_first) ; //the longer list should move diff steps if(b_first_long){ pTmp1= pFirst ; while(diff--){ pTmp1=pTmp1->next ; printf("%d+",diff) ; } pTmp2 = pSecond ; }else{ pTmp2=pSecond ; while(diff--){ pTmp2=pTmp2->next ; } pTmp1 = pFirst ; } //compute the last positon and the position = diff + last move int location=b_first_long?(len_first-len_second):(len_second-len_first) ; while(pTmp1!=pTmp2) { pTmp1=pTmp1->next ; pTmp2=pTmp2->next ; location++ ; } return location ; } void create_cross_linklist(struct _link_node* pFirst, struct _link_node *pSecond,int len1,int len2,int position){ assert(pFirst!=NULL&&pSecond!=NULL) ; struct _link_node *pTmp1 = pFirst ; struct _link_node *pTmp2 = pSecond ; int cnt = 0; if(len1>len2){ assert((len2+position)<len1) ; while(cnt<len2){ pTmp1 = pTmp1->next ; pTmp2 = pTmp2->next ; cnt++ ; } cnt=0; while(cnt<position){ pTmp1=pTmp1->next ; cnt++ ; } pTmp2->next = pTmp1 ; }else{ assert((len1+position)<len2) ; while(cnt<len1){ pTmp1 = pTmp1->next ; pTmp2 = pTmp2->next ; cnt++ ; } cnt=0 ; while(cnt<position){ pTmp2 = pTmp2->next ; cnt++ ; } pTmp1->next = pTmp2 ; } } int main() { int array[]={1,2,3,4,5,6,7,8,9,10,11,12,13,24} ; int array1[]={2,3,4,6,1,3} ; int len = sizeof(array)/sizeof(array[0]) ; int len1 = sizeof(array1)/sizeof(array1[0]) ; struct _link_node *pRoot1 = create_linklist(array,len) ; struct _link_node *pRoot2 = create_linklist(array1,len1) ; create_cross_linklist(pRoot1,pRoot2,len,len1,2) ; printf("find first cross_node begin............\n") ; printf("len=%d,len1=%d\n",len,len1) ; int location = find_first_cross_node(pRoot1,pRoot2) ; printf("first cross node at %d position\n",location) ; printf("find first cross_node end............\n\n") ; printf("binary search bound begin..........\n") ; printf("location=%d\n",binary_search1(array,0,len-1,24)) ; printf("upperbound=%d\n",binary_find_upper_bound(array,0,len-1,9)) ; printf("lowerbound=%d\n",binary_find_lower_bound(array,0,len-1,9)) ; printf("binary search bound end..........\n\n") ; printf("find reciprocal n node begin..........\n") ; struct _link_node *pRoot=create_linklist(array,len) ; struct _link_node *pTmp=get_reverse_n(pRoot,3) ; printf("data=%d\n",pTmp->data) ; printf("find reciprocal n node end..........\n") ; }