Microsoft(1) Recerse linked list by block

以前见过一个链表反转的题，这个题应该是那个的加强版，两个小时时间并不短，但要在不编译运行的前提下写出bug free的代码，对我们一般人还是不太容易的。
我看上面大家的思路都差不多，都是在反转的过程中加入对blocksize的判断，并且正确的链接各个block，我也贴一个我写的，并附上一个驱动程序用来测试和简单的测试文件。

1. #include <iostream>
   
2. #include <cstdio>
   
3. using namespace std;
   
4. typedef struct node {
   
5.         int v;
   
6.         struct node *next;
   
7.         node(int val) : v(val), next(NULL) {}
   
8.         node() : next(NULL) {}
   
9. } LNK_NODE;
   
10. LNK_NODE* ReverseByBlock(LNK_NODE* pHead, int nBlockSize)
    
11. {
    
12.         LNK_NODE *lastTail = NULL;
    
13.         LNK_NODE *curHead = pHead;
    
14.         while(curHead) {
    
15.                 LNK_NODE *preNode = NULL;
    
16.                 LNK_NODE *curNode = curHead;
    
17.                 for(int i = 0; i < nBlockSize && curNode; i++) {
    
18.                         LNK_NODE *temp = curNode->next;
    
19.                         curNode->next = preNode;
    
20.                         preNode = curNode;
    
21.                         curNode = temp;
    
22.                 }
    
23.                 if(lastTail == NULL)
    
24.                         pHead = preNode;
    
25.                 else
    
26.                         lastTail->next = preNode;
    
27.                 lastTail = curHead;
    
28.                 curHead = curNode;
    
29.         }
    
30.         return pHead;
    
31. }
    
32. void printl(LNK_NODE *head) {
    
33.         while(head) {
    
34.                 cout << head->v << " ";
    
35.                 head = head->next;
    
36.         }
    
37.         cout << endl;
    
38. }
    
39. int
    
40. main() {
    
41.         freopen("ReverseByBlock.in", "r", stdin);
    
42.         //freopen("ReverseByBlock.out", "w", stdout);
    
43.         int n;
    
44.         int nb;
    
45.         while(cin >> nb) {
    
46.                 LNK_NODE *head = NULL;
    
47.                 LNK_NODE *cur = head;
    
48.                 if(nb == -1) break;
    
49.                 while(cin >> n) {
    
50.                         if(n==-1) break;
    
51.                         LNK_NODE *nd = new LNK_NODE(n);
    
52.                         if(head == NULL) {
    
53.                                 cur = head = nd;
    
54.                         } else {
    
55.                                 cur->next = nd;
    
56.                                 cur = nd;
    
57.                         }
    
58.                 }
    
59.                 cout << "block size: " << nb << endl;
    
60.                 cout <<"Original list: ";
    
61.                 printl(head);
    
62.                 LNK_NODE *newhd = ReverseByBlock(head, nb);
    
63.                 cout <<"New list:      ";
    
64.                 printl(newhd);
    
65.                 cout << endl;
    
66.         }
    
67.         return 0;
    
68. }

复制代码

程序接收标准输入，先输入blocksize，若是-1程序结束。
然后依次输入链表的每个元素，以-1结束。-1不算做一个元素。以下是简单的测试文件，命名为ReverseByBlock.in即可。

1. 
   
2. 3
   
3. 1 2 3 4 5 6 7 8 -1
   
4. 1
   
5. 1 -1
   
6. 1
   
7. 1 2 3 4 5 6 7 -1
   
8. 3
   
9. 1 2 3 4 5 -1
   
10. 4
    
11. 1 2 3 4 5 -1
    
12. 3
    
13. 1 2 3 4 5 6 7 8 9 -1
    
14. 6
    
15. 1 2 3 4 -1
    
16. 4
    
17. -1
    
18. -1

复制代码

另外其实这题还有简练的递归解法：

1. LNK_NODE* ReverseByBlock(LNK_NODE* pHead, int nBlockSize)
   
2. {
   
3.         LNK_NODE *curNode = pHead, *preNode = NULL;
   
4.         for(int i = 0; i < nBlockSize && curNode; i++) {
   
5.                 LNK_NODE *temp = curNode->next;
   
6.                 curNode->next = preNode;
   
7.                 preNode = curNode;
   
8.                 curNode = temp;
   
9.         }
   
10.         if(curNode)
    
11.                 pHead->next = ReverseByBlock(curNode, nBlockSize);
    
12.         return preNode;
    
13. }

复制代码

我觉得链表一类的问题都是细节上容易出错的题，所以尽量减少细节和特殊情况能有效的避免出错，这对大多数题目都是适用的。一般来讲递归写起来往往比较清晰，并且不容易错。不过这也不是绝对的，面试的时候还得看对方要求，还是都掌握更加稳妥。

truct LNK_NODE
{
        int nValue;
        LNK_NODE* pNext;


        LNK_NODE(int n) : nValue(n), pNext(NULL) {}
};

LNK_NODE* reverse_n_nodes(LNK_NODE* pHead, LNK_NODE*& pNewHead ,int n)
{
        if (NULL == pHead) return NULL;


        LNK_NODE* pCur = pHead;
        LNK_NODE* pNxt = pCur->pNext;
        while (NULL != pNxt && --n)
        {
                LNK_NODE* pTmp = pNxt->pNext;
                pNxt->pNext = pCur;
                pCur = pNxt;
                pNxt = pTmp;
        }

        pNewHead = pCur;
        return pNxt;
}

LNK_NODE* ReveseBySeg(LNK_NODE* pHead ,int nSeg)
{
        assert(pHead != NULL);
        assert(nSeg > 0);
        if (1 == nSeg) return pHead;

        LNK_NODE* pRet = NULL;
        LNK_NODE* pNewHead = NULL;
        LNK_NODE* pNxtSeg = reverse_n_nodes(pHead, pNewHead, nSeg);
        pRet = pNewHead;

        //old head -> new head
        while (NULL != pNxtSeg)
        {
                LNK_NODE* pNewTail = pNxtSeg;
                pNxtSeg = reverse_n_nodes(pNxtSeg, pNewHead, nSeg);
                pHead->pNext = pNewHead;
                pHead = pNewTail;
        }
        pHead->pNext = NULL;


        return pRet;
}

回复 12# darksteel
赞 个人也觉得recursive的方法比较好想 不容易出错  不用递归则需要分别记住反转子链表的分界结点指针 有点晕菜想不清楚了... 另想问i初始值是从0开始么？

回复 14# tango
嗯，应该是的，具体代入blocksize为1、2的情况想一下就行。另外我这也是测试过的。
这题我自忖要在面试的时候碰到，是写不太好的，欠缺的还很多啊。