チェーン表シリーズの文章(二)

前の文章はチェーンの基本的なデータ構造を実現しました.
まず、リンクノードのデータ構造を示します.

1 struct ListNode {

2     int var;

3     ListNode *next;

4     ListNode(int v = 0 ) : var(v), next(NULL) {  }

5 };

 
1.チェーンの最後からK番目のノードを削除する
例えば、与えられたチェーンテーブル:1->>2->>3->>4->5,n=5は、2->3->4->5方法の1つに戻ります.従来のやり方では、2回のスキャンで、最初のスキャンでチェーンの長さを得て、削除されるノードの順方向インデックスを求めて、第2回のスキャンでノードを削除します.
時間複雑度O(n)、空間複雑度O(1)

 1 ListNode *removeNthNodeFromEndOfList(ListNode *head, int k) {

 2     if( !head || k < 1 ) return NULL;

 3     int len = 0;

 4     ListNode *p = head, newhead(-1);

 5     newhead.next = p;

 6     for( ; p; p = p->next ) len++;//     ,      

 7     k = len - k;//               

 8     if(k < 0) return NULL;

 9     p = &newhead;

10     while( k-- ) p = p->next;//     ，             

11     

12     ListNode *tmp = p->next;

13     p->next = tmp->next;

14     delete tmp;

15     return newhead.next;

16 }

方法2:2つのポインタ、1番目のポインタは先にK歩、そして2つのポインタは同時に進み、2番目のポインタがリンクの最後に来たとき、最初のポインタが指すノードは削除されるノードです.
時間複雑度O(n)、空間複雑度O(1)

 1 ListNode *removeNthNodeFromEndOfList(ListNode *head, int k) {

 2     if(!head || k < 1)    return NULL;

 3     ListNode newhead(-1), *p = &newhead, *q = &newhead;

 4     newhead.next = head;      

 5     while( k-- && q ) q = q->next; //q->next     k   

 6     if( !q ) return NULL;

 7     while( p && q->next ) { p = p->next; q = q->next; }//p->next        

 8     q = p->next;

 9     p->next = q->next;

10     delete q;

11     return newhead.next;

12 }

 
2.  ランダムポインタ付きのチェーンテーブルをコピーします.ランダムポインタは、チェーンテーブルのノードを指しますか?それとも空ですか?

1 struct RandomListNode {

2     int var;

3     RandomListNode *next, *random;

4     RandomListNode(int v) : var(v), next(NULL), random(NULL) { }

5 };

方法1:従来のやり方で、まずチェーンをスキャンしてnextポインタをコピーする.その後、各ノードに対して、ランダムノードのチェーンテーブル内のインデックスを特定し、各randomノードをコピーする際に、nextポインタをスキャンする.
インデックスに対応するノードが得られ、そのノードに対してランドマークポインタが向けられます.
時間複雑度O(n 2)、空間複雑度O(n)

 1 RandomListNode *copyRandomList(RandomListNode *head) {

 2     if( !head ) return NULL;

 3     int n = 0;

 4     RandomListNode *p = head, newhead(-1), r = &newhead;

 5     for( ; p; p = p->next ) {//    ，  next  ,        

 6         r->next = new RandomListNode(p->var);

 7         r = r->next; n++;

 8     }

 9     r = &newhead;

10     for(p = head; p; p = p->next) {//    random  

11         if(NULL == p->random)

12             r->next->random = NULL;

13         else if(p->random == p)

14             r->next->random = r->next;

15         else {//          

16             int k = n;

17             RandomListNode *q = p->random;

18             RandomListNode *h = newhead.next;

19             while(q) {k--; q = q->next;}//random          

20             while(k--) {h = h->next;}//           

21             r->next->random = h;

22         }

23         r = r->next;

24     }

25     return newhead.next;

26 }

 
方法2:チェーンテーブルをコピーしたノードをソースチェーンの対応ノードに1つずつ挿入した後、
ソースチェーン(nextポインタのみ表示):s 1->s2->s3->s 4
挿入後:s 1->>d 1->>s 2->s 3->d 3->s 4->d 4をコピーします.例えば、d 1のランドムポインタをコピーするには、d 1->ランドm=s 1->ランドm->nextだけでいいです.
時間複雑度O(n)、空間複雑度O(n)

 1 RandomList *copyRandomList(RandomListNode *head) {

 2     if( !head ) return NULL;

 3     RandomListNode newhead(-1);

 4     for( RandomListNode* p = head; p != NULL ) { //                   

 5         RandomListNode* q = new RandomListNode(p->var);

 6         q->next = p->next;

 7         p->next = q;

 8         p = q->next;

 9     }

10     for( RandomListNode* p = head; p != NULL ) {//  random  

11         if (p->random != NULL)

12             p->next->random = p->random->next;

13         p = p->next->next;

14     }

15     for( RandomListNode* p = head, *d_p = &newhead; p != NULL ) {//      

16         d_p->next = p->next;

17         d_p = d_p->next;

18         p->next = p->next->next;

19         p = p->next;

20     }

21     return newhead.next;

22 }

 
3.チェーン時計に環があるかどうかを判断し、もしあれば、交点を見つけます.
判断にリングがある:
方法1:hashは、hashテーブルでノードごとのアドレスを記録し、最初にhash値が存在するとき、交差を示し、同時に最初のノードを見つけました.そうでなければ、空に行くと交点がありません.
             時間複雑度O(n)、空間複雑度O(n)
方法2:減速の針、fastの針は毎回2歩を歩いて、slowの針は毎回1歩を歩いて、だからfastの針はslow針に対して毎回1つ歩いて、もし環があるならば、きっと有限な歩で交差して、交点を判断しますと、博文を参考にします:
             http://www.cnblogs.com/carlsama/p/4127201.html
 
私のレベルが限られていますので、文章の中には避けられないところがあります.