|
1.已知鏈表的頭結點head,寫一個函數(shù)把這個鏈表逆序 - void 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;
- }
遞歸方法： - void 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.已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序。 - void 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;
- }
-
- }
- }
遞歸方法: - list_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.有一個鏈表L,其每個節(jié)點有2個指針，一個指針next指向鏈表的下個節(jié)點，另一個random隨機指向鏈表中的任一個節(jié)點，可能是自己或者為空，寫一個程序，要求復制這個鏈表的結構并分析其復雜性 這個題目的方法很巧妙，將兩個鏈表連接起來形成一個鏈表，設置好random指針后再將兩個鏈表分割開來。  - List 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;
- else
- cur->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. 找出單向鏈表中中間結點 兩個指針，一個步長為1，另一個步長為2.步長為2的走到底后步長為1的正好到中間。 - list_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. 如何檢查一個單向鏈表上是否有環(huán) 同樣兩個指針，一個步長為1，另一個步長為2，如果兩個指針能相遇則有環(huán)。 - list_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án)的第一個節(jié)點。 設鏈表頭到環(huán)入口節(jié)點距離為x，環(huán)入口節(jié)點到兩個指針相遇節(jié)點距離為z，換長度為y，則有x+z+1=y,所以z=y-1-x，即一個指針從鏈表頭部開始移動，一個指針兩個指針相遇后一個節(jié)點開始移動，相遇的地方即為環(huán)入口 - list_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.只給定單鏈表中某個結點p(并非最后一個結點，即p->next!=NULL)指針，刪除該結點。 將p后面那個節(jié)點的值復制到p，刪除p后面的節(jié)點 - void List::deleteByPointer(list_node * node)
- {
- if(node)
- {
- if(node->next){
- node->value = node->next->value;
- node->next = node->next->next;
- }
- }
- }
8.在p前面插入一個節(jié)點 在p后面插入新節(jié)點，將p的值與新建的節(jié)點值互換。 9.給定單鏈表頭結點，刪除鏈表中倒數(shù)第k個結點 一個指針指向鏈表頭，另一個指針指向第k個指針，然后兩個指針一起移動，第二個指針到了末端則第一個指針就是倒數(shù)第k個節(jié)點 | 
