博客

这题本想直接百度的，结果百度一看全是关于链表逆置的，没有分段逆置，所以就自己写了一个，分享给大家，第一次写博客，也不知道写的怎么样，如果哪里有错欢迎大家指出…

3-5 单链表分段逆转 (20 分)

给定一个带头结点的单链表和一个整数K，要求你将链表中的每K个结点做一次逆转。例如给定单链表 1→2→3→4→5→6 和 K=3，你需要将链表改造成 3→2→1→6→5→4；如果 K=4，则应该得到 4→3→2→1→5→6。

函数接口定义:

void K_Reverse( List L, int K );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是带头结点的单链表，K是每段的长度。函数K_Reverse应将L中的结点按要求分段逆转。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

List ReadInput(); /* 裁判实现，细节不表 */
void PrintList( List L ); /* 裁判实现，细节不表 */
void K_Reverse( List L, int K );

int main()
{
    List L;
    int K;

    L = ReadInput();
    scanf("%d", &K);
    K_Reverse( L, K );
    PrintList( L );

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例:

6
1 2 3 4 5 6
4

输出样例：

4 3 2 1 5 6

我们先来理一下解题的思路：

1.首先我们需要理解分段逆转的意思，并不是题给实例那样仅仅将链表的前面K个数据逆转了；而是，如果链表数据个数远大于K个是我们要把每K个数据都要逆置一下。比如我们输入的是4，1，2，3，4，5，6，7，8，9，10，则输出结果就为4，3，2，1，8，7，6，4，9，10。大家注意如果最后有不足K个的数据不需要逆置。

2.我们需要考虑一下程序的健壮性，就是写这个程序时要考虑那些条件:

1.首先就要考虑k的正确性，当K小于0的时候当然时不行的；如果K等于1链表不会发生
变化，所以我们可以将这种情况和K=0时放在一起，还有一种情况就是K的值大于
链表数据总数时，链表也不会变，所以这种情况也要排除。
2.我们要注意一下题目给的函数的声明方式，他没有给返回值，只给了两个参数，一个
是K，一个是链表的头指针L。注意：这里是指针，而不是指针的指针，也就是二级指针。
所以如果我们在新建一个链表Head，把L逐个copy并分段逆置到Head里，在令L=Head，
这样做是不对的，因为我们对L进行改变不会影响到函数外面的改变。就像基本数据类型
传递一样，所以我们只能在L的基础上进行改变，即不能再新建头指针。
这些都是我在写的时候想到的一些情况，也许没全，但是足以过题了。
3.看到这题我们第一时间就会想到双重循环，所以这题理所应当的用双重循环来写，
下面我们就来看下代码的具体操作顺序；

我的代码

//我们这里就假设K为4；

void K_Reverse( List L, int K )
{
    PtrToNode r, p, end1,end2 ,H = L->Next;//_ 1 2 3 4 5 6 7 8 9 10  11 12    
    /**end1和end2是用来连接两个逆置后的分段；
       一开始我们令end1指向头节点，end2指向数据1所在的节点，为什么这样做呢？
       因为前四个数据我们都要把他以头插入方式插到L后面，也就是end1后面；
       当我们遍历到节点5的时候我们需要令end1 = end2；end2 = 5所在的节点；
       然后我们需要将5 6 7 8再以头插入的方式插入到1节点的后面，也就是end1的后面
       也就是说我们一直将节点以头插入的方式插入到end1后面，而end2使用来记录下一个
       分段的第一个节点，也就是下一个end1，就这样不断更新end1就可以实现将整个链表
       分段逆置；这是end1和end2的作用
    */
    end1 = L；
    end2 = L->Next;
    r = L->Next;	//用来遍历链表
    p = r->Next;    
    int count = 0;      
    /**
    	count用来记录链表节点总数；
    	为什么要记录总数？
    	因为我们要知道链表最后一个分段是不足K个节点，还是刚好K个节点；
    	如果不足就不用逆置，如果刚好也要把这一分段逆置了；
    */
    if (K>=1)		    //这里就是我上面说的考虑K的情况
    {    
    	//记录总数
        while (H)        
        {            
        count++;            
        H = H->Next;        
        }
                
        //判断，如果总数小于K就不变链表
        if (count>=K)        
        {
       	    /**count/K是我们总共需要循环几个分段，因为count/K结果去商，
       	       所以如果count不能被K整除，即最后一个分段不足K个，我们就不循环
       	       也就是不动它。
       	    */            
            for (int j = 0;j<count/K;j++)            
            {                
            	//每个分段循环K次
                for(int i = 0; i < K; i++)                
                {                    
                    r->Next = end1->Next;	//头插入
                    end1->Next = r;
                    r = p;
                    /**
                     这里为什么要判断p不为空呢？
                     因为我一开令r = L->Next;
                     		p = r->Next;
                     所以最后p会指向链表最后的Next域，而Next为空，就不
                     存在p的Next域，如果不判断的话程序运行到此处就不会再运行下去
                     而程序一开始编译的时候不会报错，所以这一点很重要，即判断越界
                     问题，我也是找了很长时间才找点这一点。
                    */                      
                    if(p)
                        p = p->Next;                
                 }
                end1 = end2;	//更新end1和end2                
                end2 = r;            
            }            
            end1->Next = r;	//最后将尾节点Next域置空。
        }
    }
}