免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

1.已知鏈表的頭結(jié)點(diǎn)head,寫(xiě)一個(gè)函數(shù)把這個(gè)鏈表逆序[cpp] view plaincopyvoid List::reverse(){list_node * p = head;list_node * q = p->next;list_node * r = NULL;while(q){r = q->next;q->next = p;p = q;q = r;}head->next  = NULL;head = p;}遞歸方法：[cpp] view plaincopyvoid List::reverse2(list_node * curnode){if(curnode ==NULL)curnode = head;if(curnode->next==NULL){cur = curnode;return;}reverse2(curnode->next);curnode->next->next=curnode;if(curnode == head){head=cur;cur = curnode;cur->next = NULL;}}2.已知兩個(gè)鏈表head1 和head2 各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。[cpp] view plaincopyvoid List::merge(List & list){list_node * a = head;list_node * b = list.head;list_node * tempa= a;list_node * tempb = b;while(a&&b){if(a->value <= b->value){while(a&&b&&a->value <= b->value){tempa = a;a = a->next;}tempa->next=b;}else{while(a&&b&&a->value > b->value){tempb = b;b = b->next;}tempb->next=a;}}}遞歸方法:[cpp] view plaincopylist_node* List::recursive_merge(list_node * a,list_node * b){if(a == NULL)return b;if(b == NULL)return a;if(a->value <= b->value){a->next=recursive_merge(a->next,b);return a;}if(a->value > b->value){b->next=recursive_merge(a,b->next);return b;}}3.有一個(gè)鏈表L,其每個(gè)節(jié)點(diǎn)有2個(gè)指針，一個(gè)指針next指向鏈表的下個(gè)節(jié)點(diǎn)，另一個(gè)random隨機(jī)指向鏈表中的任一個(gè)節(jié)點(diǎn)，可能是自己或者為空，寫(xiě)一個(gè)程序，要求復(fù)制這個(gè)鏈表的結(jié)構(gòu)并分析其復(fù)雜性這個(gè)題目的方法很巧妙，將兩個(gè)鏈表連接起來(lái)形成一個(gè)鏈表，設(shè)置好random指針后再將兩個(gè)鏈表分割開(kāi)來(lái)。[cpp] view plaincopyList List::copyRndList(){list_node * newhead = NULL;list_node * newcur = NULL;list_node * cur = head;while(cur){if(newhead == NULL){newhead = new list_node;newhead->value = cur->value;newhead->next = cur->next;cur->next = newhead;}else{newcur = new list_node;newcur->value = cur->value;newcur->next = cur->next;cur->next = newcur;}cur=cur->next->next;}cur = head;while(cur){if(cur->rnd)cur->next->rnd=cur->rnd->next;elsecur->next->rnd = NULL;cur = cur->next->next;}cur = head;list_node * dst = cur->next;while(cur){list_node * temp = dst->next;cur->next = temp;if(temp)dst->next = temp->next;cur = cur->next;dst=dst->next;}List newList;newList.head = newhead;return newList;}4. 找出單向鏈表中中間結(jié)點(diǎn)兩個(gè)指針，一個(gè)步長(zhǎng)為1，另一個(gè)步長(zhǎng)為2.步長(zhǎng)為2的走到底后步長(zhǎng)為1的正好到中間。[cpp] view plaincopylist_node * List::middleElement(){list_node * p = head;list_node * q = head->next;while(q){p = p->next;if(q)q=q->next;if(q)q=q->next;}}5. 如何檢查一個(gè)單向鏈表上是否有環(huán)同樣兩個(gè)指針，一個(gè)步長(zhǎng)為1，另一個(gè)步長(zhǎng)為2，如果兩個(gè)指針能相遇則有環(huán)。[cpp] view plaincopylist_node * List::getJoinPointer(){if(head == NULL || head->next == NULL)return NULL;list_node * one = head;list_node * two = head->next;while(one != two){one = one->next;if(two)two=two->next;else break;if(two)two=two->next;else break;}if(one == NULL || two == NULL)return NULL;return one;}6. 給定單鏈表(head)，如果有環(huán)的話(huà)請(qǐng)返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。設(shè)鏈表頭到環(huán)入口節(jié)點(diǎn)距離為x，環(huán)入口節(jié)點(diǎn)到兩個(gè)指針相遇節(jié)點(diǎn)距離為z，換長(zhǎng)度為y，則有x+z+1=y,所以z=y-1-x，即一個(gè)指針從鏈表頭部開(kāi)始移動(dòng)，一個(gè)指針兩個(gè)指針相遇后一個(gè)節(jié)點(diǎn)開(kāi)始移動(dòng)，相遇的地方即為環(huán)入口[cpp] view plaincopylist_node * List::findCycleEntry(){if(checkCycle()==false)return NULL;list_node * joinPointer = getJoinPointer();list_node * p = head;list_node * q = joinPointer->next;while(p!=q){p=p->next;q=q->next;}return p;}7.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)，即p->next!=NULL)指針，刪除該結(jié)點(diǎn)。將p后面那個(gè)節(jié)點(diǎn)的值復(fù)制到p，刪除p后面的節(jié)點(diǎn)[cpp] view plaincopyvoid List::deleteByPointer(list_node * node){if(node){if(node->next){node->value = node->next->value;node->next = node->next->next;}}}8.在p前面插入一個(gè)節(jié)點(diǎn)在p后面插入新節(jié)點(diǎn)，將p的值與新建的節(jié)點(diǎn)值互換。9.給定單鏈表頭結(jié)點(diǎn)，刪除鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)一個(gè)指針指向鏈表頭，另一個(gè)指針指向第k個(gè)指針，然后兩個(gè)指針一起移動(dòng)，第二個(gè)指針到了末端則第一個(gè)指針就是倒數(shù)第k個(gè)節(jié)點(diǎn)[cpp] view plaincopylist_node * List::lastKelement(int k){int t = k;list_node * p = head;while(p&&t){p=p->next;t--;}if(p == NULL && t >0)return NULL;list_node * q=head;while(q && p){p=p->next;q=q->next;}return q;}10. 判斷兩個(gè)鏈表是否相交。兩種情況，如果鏈表有環(huán)，則先在環(huán)里設(shè)定一個(gè)指針不動(dòng)，另一個(gè)鏈表從頭開(kāi)始移動(dòng)，如果另一個(gè)鏈表能夠與環(huán)中的指針相遇則是相交。如果沒(méi)有環(huán)，則判斷兩個(gè)鏈表的最后個(gè)節(jié)點(diǎn)是否相同，相同則相交[cpp] view plaincopybool List::isIntersecting(const List & list){bool flag = false;if(this->checkCycle()){list_node * p = getJoinPointer();list_node * q = list.head;while(q){if(q == p){flag = true;break;}q=q->next;}flag = true;}else{list_node * p = head;list_node * q = list.head;while(p->next)p=p->next;while(q->next)q=q->next;if(p  == q)flag = true;else flag =false;}return flag;}11. 兩個(gè)鏈表相交，找出交點(diǎn)求出兩個(gè)鏈表的長(zhǎng)度a和b，一個(gè)指針指向較短鏈表的頭head，另一個(gè)指針指向較長(zhǎng)鏈表的第head+|a-b|，然后兩個(gè)指針一起移動(dòng)，相遇處即為交點(diǎn)。[cpp] view plaincopylist_node * List::intersectNode(const List & list){if(!isIntersecting(list))return NULL;int a = cnt;int b = list.cnt;list_node * p;list_node * q;if(a<b){p=list.head;q = head;}else {p = head; q=list.head;}a = abs(cnt - list.cnt);while(p && a){p = p->next;a--;}while(p&&q){if(q==p)break;p=p->next;q=q->next;}if(p && q && p == q)return p;return NULL;}