Microsoft(1) Recerse linked list by block

//Reverse linklist in block
//eg. block size is 3 and list is
//1 2 3 4 5 6 7 8
//Output: 3 2 1 6 5 4 8 7

LNK_NODE*  ReverseByBlock(LNK_NODE* pHead ,int nBlockSize)

这个题方法大家都知道。
计个时，看看谁能做到在两小时内写出无bug的代码，请上代码，自附testcase

我猜肯定有错，没有空看了@@
update：果然有变量没赋初值。。。
update：被GG指出来pointer定义时忘记在answer前写*了>_<

1. LNK_NODE*  ReverseByBlock(LNK_NODE* pHead ,int nBlockSize)
   
2. {
   
3. 
   
4.         LNK_NODE* head = NULL, *answer = NULL;
   
5.         while (pHead != NULL)
   
6.         {
   
7.                 LNK_NODE* temp = NULL;
   
8.                 for (int i = 0; i < nBlockSize; ++i)
   
9.                 {
   
10.                         if (pHead == NULL) break;
    
11.                         LNK_NODE* SwapPt = pHead;
    
12.                         pHead = pHead->next;
    
13.                         SwapPt->next = temp;
    
14.                         temp = SwapPt;
    
15.                 }
    
16.                 if (head == NULL)
    
17.                 {
    
18.                         head = temp;
    
19.                         answer = temp;
    
20.                 }
    
21.                 else
    
22.                         answer->next = temp;
    
23.                 while (answer->next != NULL)
    
24.                         answer = answer->next;
    
25.         }
    
26.         return head;
    
27. }

复制代码

这种计时的方式挺好的，我觉得以后人气高了可以定期或者不定期组织限时比赛- -

算了还是干脆做一个online judge系统好了- -

不过像我们这种面向招工的版块，还是不要太ACM化的比较好

扯远了。。。继续重装VS2010去了。。真蛋疼

回复 3# 一剑终情

OJ我觉得不用。。。
OJ那么多，比赛也很多。。。
而且对面试来说有些能力是不需要的吧@@
比如快速读题和疯狂找弱题@@
我也扯远了。。。

我觉得可以每天定时发几道题，限时不限时都ok~
每天跟着做肯定会有进步的～～

回复 4# vvnesaa


    是。。我写着写着也发现其实没必要。。
我这个帖子就是一个自己立论然后又自己驳论的过程。。

我猜肯定有错，没有空看了@@
update：果然有变量没赋初值。。。
update：被GG指出来pointer定义时忘记在a ...
vvnesaa 发表于 2011-4-18 14:31

    错误那是相当多

回复 6# wwwyhx

啊。。。现在还有错哦@@
啥错，跪求指导！

这种计时的方式挺好的，我觉得以后人气高了可以定期或者不定期组织限时比赛- -

算了还是干脆做一个onlin ...
一剑终情 发表于 2011-4-18 15:31

你现在可以逐渐college ideas，开版过段时间之后，大家可以再合计，想想可以做哪些改进。

写了一个超级囧的 ，都忘了用nBlockSize了。。。

1. LNK_NODE*  ReverseByBlock(LNK_NODE* pHead ,int nBlockSize)
   
2. {
   
3.         LNK_NODE *last = pHead;
   
4.         LNK_NODE *index = pHead;
   
5.         short flag = 0;
   
6.         bool end = 0;
   
7. 
   
8.         while (!end)
   
9.         {
   
10.                 flag = 0;
    
11.                 while (flag < 3 && index->next != NULL)
    
12.                 {
    
13.                         index = index->next;
    
14.                         flag++;
    
15.                 }
    
16. 
    
17.                 switch (flag)
    
18.                 {
    
19.                         case 3:
    
20.                                 LNK_NODE *begin = NULL;
    
21.                                 LNK_NODE *mid = NULL;
    
22.                                 LNK_NODE *end = NULL;
    
23.                                 LNK_NODE *temp = NULL;
    
24.                                
    
25.                                 end = last->next;
    
26.                                 mid = end->next;
    
27.                                 begin = mid->next;
    
28. 
    
29.                                 temp = begin->next;
    
30.                                 last->next = begin;
    
31.                                 begin->next = mid;
    
32.                                 mid->next = end;
    
33.                                 end->next = temp;
    
34. 
    
35.                                 last = end;
    
36.                                 break;
    
37. 
    
38.                         case 2:
    
39.                                 LNK_NODE *begin = NULL;
    
40.                                 LNK_NODE *end = NULL;
    
41. 
    
42.                                 end = last->next;
    
43.                                 begin = end->next;
    
44. 
    
45.                                 last->next = begin;
    
46.                                 begin->next = end;
    
47.                                 end->next = NULL;
    
48. 
    
49.                                 end = 1;
    
50.                                 break;
    
51. 
    
52.                         case 1:
    
53.                         case 0:
    
54.                                 end = 1;
    
55.                                 break;
    
56.                 }
    
57.         }
    
58.         return pHead;
    
59. }

复制代码

写的累死啦！无注释。。。

1. //Reverse linklist in block
   
2. //eg. block size is 3 and list is
   
3. //1 2 3 4 5 6 7 8
   
4. //Output: 3 2 1 6 5 4 8 7
   
5. #include <iostream>
   
6. using namespace std;
   
7. 
   
8. class LNK_NODE
   
9. {
   
10. public:
    
11.      int element;
    
12.      LNK_NODE *next;
    
13.      LNK_NODE(const int& elem, LNK_NODE* nextval = NULL)
    
14.           {element = elem; next = nextval;}
    
15. };
    
16. 
    
17. LNK_NODE* ReverseByBlock(LNK_NODE* pHead ,int nBlockSize)
    
18. {
    
19.      if(!pHead)
    
20.           return NULL;
    
21.      LNK_NODE* hn = new LNK_NODE(-1);
    
22.      hn->next = pHead;
    
23.      LNK_NODE* ih = hn;
    
24.      while(true)
    
25.      {
    
26.           LNK_NODE* np = ih->next;
    
27.           LNK_NODE* ip = ih;
    
28.           int i;
    
29.           for(i = 0; i < nBlockSize; i++)
    
30.           {
    
31.                if(np == NULL)
    
32.                     break;
    
33.                LNK_NODE* temp = np;
    
34.                np = np->next;
    
35.                temp->next = ip;
    
36.                ip = temp;
    
37.           }
    
38.           LNK_NODE* temp = ih->next;
    
39.           if(ih->next != NULL)
    
40.                ih->next->next = np;
    
41.           ih->next = ip;
    
42.           ih = temp;
    
43.           if(i != nBlockSize)
    
44.                break;          
    
45.           if(np == NULL)
    
46.                break;
    
47.      }
    
48.      pHead = hn->next;
    
49.      delete hn;
    
50.      return pHead;
    
51. }
    
52. 
    
53. LNK_NODE* create(int size)
    
54. {
    
55.      if(size == 0)
    
56.           return NULL;
    
57.      LNK_NODE* t= new LNK_NODE(0, NULL);
    
58.      LNK_NODE* h = t;
    
59.      for(int i = 1; i < size; i++)
    
60.           t = t->next = new LNK_NODE(i, NULL);
    
61.      return h;
    
62. }
    
63. void print(LNK_NODE* h)
    
64. {
    
65.      while(h!=NULL)
    
66.      {
    
67.           cout << h->element << endl;
    
68.           LNK_NODE* t = h;
    
69.           h = h->next;
    
70.           delete t;
    
71.      }
    
72.      cout << "test case finished----" << endl;
    
73. }
    
74. 
    
75. int main()
    
76. {
    
77.      for(int i = 1; i <= 10; i++)
    
78.      {
    
79.           LNK_NODE* h = create(10);
    
80.           h = ReverseByBlock(h,i);
    
81.           print(h);
    
82.      }
    
83.      return 0;
    
84. }
    

复制代码