02-线性结构3 Reversing Linked List(PTA)

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10​5​​) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, andNext is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

Author: 陈越

Organization: 浙江大学

Time Limit: 400ms

Memory Limit: 64MB

Code Size Limit:16KB

初学数据结构， 十分惭愧， 这道题虐了我好几天；

但是最后一遍直接AC的感觉是十分美妙的；

现在对此题做些总结：

（一）单链表的倒转

本来一开始， 以我个人的性格， 总是喜欢自己研究， 结果搞了好几天都是各种段错误， 语法错误；

还误入歧途， 尝试了双向链表， 极其繁琐， 又不易调试；

而后终于， 借鉴https://www.2cto.com/kf/201601/485759.html博客的思想， 在链表倒转这一块算是有了较好的认识；

（二）采用递归

在第四个版本时， 重新架构代码；

重新思考题目， 发现无论如何， 都要遍历一次， 按顺序安放结点；

那么为何不把问题主要分解成：

1.根据地址找到结点；

2.将其放到正确的位置；

而显然， 要遍历到K == 1 或者 Address 找不到， 方可知道要采用倒转放置， 还是正序放置；

故递归做法， 显然是十分合适的；

当递归至最里层， 根据递归返回状态， 选择是要倒序， 还是正序；

而后层层回溯， 放置结点；

故总体时间复杂度为O(n)；
n为结点地址为-1或找不到为止；
小于等于链表长度；
空间复杂度， 因有递归， 不是很懂， 当K较大时， 递归层数较深， 或许会较大；
但， 不考虑递归带来的影响， S(n)；
n为总链表长度；

总结：

最后的时候， 一次性写完代码， 除了几个分号不小心为中文的， 其余没有错误， 一次性编译通过；

真的是十分的爽快；

在sublime上简单的测试了一下， 发现没有什么问题， 便上交PTA；

最后一次AC！

还是太弱， 小题目就花了好几天；

不过这道题下来， 对链表的使用确实有了很大的提升；

最后， 附代码：

/**********************/
/*    Title:
        Reversing_Linked_list_v0_4
/*    Author:
        cxy
/*    Start_Date:
        04242018
/*    Finished_Date:
        04242018
/*    FUNCTION:
        主要实现了，给定一系列的数据， 用单链表存储， 而后根据结点信息， 对应其内部排列关系， 进行给定位数的结点次序反转。
        一直反转到无法反转；
        输入：
        地址， 数据， 下一节点地址；
        输出：
        按行：地址， 数据， 下一节点地址；

        具体可见https://pintia.cn/problem-sets/951072707007700992/problems/972813177016877056
/*    Details:
        采用递归思想, 重新规划架构;
        避免前面版本的拖沓;
        无论如何， 都要遍历一次， 要重新排序；
        就是说， 在遍历同时， 直接考虑其位置；
        则共需遍历一次；
        故总体时间复杂度为O(n)；
        n为结点地址为-1或找不到为止；
        小于等于链表长度；
        空间复杂度， 因有递归， 不是很懂， 当K较大时， 递归层数较深， 或许会较大；
        但， 不考虑递归带来的影响， S(n)；
        n为总链表长度；
/**********************/

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

#define ERROR_FIRST 1
#define ERROR         2
#define OK             3
#define WRONG        0

typedef int STATUS;
typedef struct LL_Node *p_llnode;
typedef struct Detail information;

struct Detail
{
    int Address;
    int Data;
    int Next;
};

struct LL_Node
{
    information node;
    p_llnode link;
};

p_llnode Read_List( int total_num );
p_llnode Reverse_List( p_llnode L, int start_address, int rev_num );
void Print_List( p_llnode L );
void Attach( p_llnode *rear, information INF );
STATUS Sub_Rev_List( p_llnode head, int *Address, int rev_num, p_llnode sub_list_head, p_llnode *sub_list_rear );
p_llnode Get_Needed_Node( p_llnode head, int Address );
void Get_Sub_FIRST_Head( p_llnode p_needed_node, p_llnode sub_list_head, p_llnode *sub_list_rear );
void Head_Insert( p_llnode p_needed_node, p_llnode sub_list_head );
void Rear_Insert( p_llnode p_needed_node, p_llnode *sub_list_rear );
void FREE_Left_Node( p_llnode head );
void Reindex_LLnode( p_llnode L );

int main(int argc, char const *argv[])
{
    p_llnode L = NULL;
    int start_address = 0, total_num = 0, rev_num = 0;

    scanf("%d %d %d", &start_address, &total_num, &rev_num);

    L = Read_List( total_num );
    L = Reverse_List( L, start_address, rev_num );

    Reindex_LLnode( L );
    Print_List( L );

    return 0;
}

p_llnode Read_List( int total_num )
{
    information INF;
    p_llnode head, rear, temp = NULL;

    if ( total_num <= 0)
        return NULL;

    rear = head = (p_llnode)malloc(sizeof(struct LL_Node));

    while ( total_num-- )
    {
        scanf("%d %d %d", &INF.Address, &INF.Data, &INF.Next);
        Attach( &rear, INF );
    }
    rear->link = NULL;

    temp = head;
    head = head->link;
    free(temp);

// test_read
    // temp = head;
    // while ( head )
    // {
    //     printf("%05d %d %05d\n", head->node.Address, head->node.Data, head->node.Next);
    //     head = head->link;
    // }

    return head;
}

// recursion;
p_llnode Reverse_List( p_llnode L, int start_address, int rev_num )
{
    p_llnode head, new_list_head, new_list_rear, sub_list_head, sub_list_rear, temp;
    int Address = start_address;
    int IS_FIRST_SUB_REV = 1;

    new_list_head = new_list_rear = sub_list_head = sub_list_rear = NULL;

    head = (p_llnode)malloc(sizeof(struct LL_Node));
    head->link = L;

    sub_list_head = (p_llnode)malloc(sizeof(struct LL_Node));
    sub_list_head->link = NULL;

    while ( Sub_Rev_List( head, &start_address, rev_num, sub_list_head, &sub_list_rear ) == OK )
    {
        if ( IS_FIRST_SUB_REV )
        {
            IS_FIRST_SUB_REV = 0;
            new_list_head = sub_list_head->link;        // new_list_head不带头空结点;
        }
        else
            new_list_rear->link = sub_list_head->link;
            
        new_list_rear = sub_list_rear;

        sub_list_head->link = NULL;
    }

    new_list_rear->link = sub_list_head->link;
    new_list_rear = sub_list_rear;
    // new_list_rear->link = NULL;
    FREE_Left_Node( head );
    free( head );
    free( sub_list_head );

    return new_list_head;
}

void Print_List( p_llnode L )
{
    while ( L->node.Next != -1 )
    {
        printf("%05d %d %05d\n", L->node.Address, L->node.Data, L->node.Next);
        L = L->link;
    }
    printf("%05d %d %d\n", L->node.Address, L->node.Data, L->node.Next);
}

void Attach( p_llnode *rear, information INF )
{
    p_llnode temp;

    temp = (p_llnode)malloc(sizeof(struct LL_Node));

    // temp->node = *INF? 结构体直接赋值， 可能会有问题; 虽然test时是OK的， 此点保留意见;
    temp->node.Address = INF.Address;
    temp->node.Data = INF.Data;
    temp->node.Next = INF.Next;
    temp->link = NULL;

    (*rear)->link = temp;
    *rear = temp;
}

STATUS Sub_Rev_List( p_llnode head, int *Address, int rev_num, p_llnode sub_list_head, p_llnode *sub_list_rear )
{
    p_llnode temp, p_needed_node;
    STATUS rev_status;

    p_needed_node = Get_Needed_Node( head, *Address );
    if ( !p_needed_node )        // Sub_Rev非正常终止信号; 此时表示所给Address无法指定结点， 也可能为-1;
        return ERROR_FIRST;

    *Address = p_needed_node->node.Next;        // 更新Address;

    if ( rev_num == 1 )    // Sub_Rev正常终止信号;
    {
        Get_Sub_FIRST_Head( p_needed_node, sub_list_head, sub_list_rear );
        return OK;
    }

    --rev_num;

    rev_status = Sub_Rev_List( head, Address, rev_num, sub_list_head, sub_list_rear );
    switch ( rev_status )
    {
        case ERROR_FIRST:
            Get_Sub_FIRST_Head( p_needed_node, sub_list_head, sub_list_rear );
            return ERROR;

        case ERROR:
            Head_Insert( p_needed_node, sub_list_head );    // 注意! sub_list_head是p_llnode型;
            return ERROR;

        case OK:
            Rear_Insert( p_needed_node, sub_list_rear );    // 注意! sub_list_rear是p_llnode *型;
            return OK;

        default:
            return WRONG;
    }
}

p_llnode Get_Needed_Node( p_llnode head, int Address )
{
    p_llnode p_front_node, temp;

    p_front_node = head;

    while ( p_front_node->link && p_front_node->link->node.Address != Address )
        p_front_node = p_front_node->link;

    if ( !p_front_node->link )
        return NULL;

    temp = p_front_node->link;
    p_front_node->link = temp->link;
    temp->link  = NULL;

    return temp;
}

void Get_Sub_FIRST_Head( p_llnode p_needed_node, p_llnode sub_list_head, p_llnode *sub_list_rear )
{
    *sub_list_rear = sub_list_head->link = p_needed_node;
}

void Head_Insert( p_llnode p_needed_node, p_llnode sub_list_head )
{
    p_needed_node->link = sub_list_head->link;
    sub_list_head->link = p_needed_node;
}

void Rear_Insert( p_llnode p_needed_node, p_llnode *sub_list_rear )
{
    (*sub_list_rear)->link = p_needed_node;
    *sub_list_rear = p_needed_node;
}

void FREE_Left_Node( p_llnode head )
{
    p_llnode temp;

    while ( head->link )
    {
        temp = head->link;
        head->link = temp->link;
        free(temp);
    }
}

void Reindex_LLnode( p_llnode L )
{
    while ( L->link )
    {
        L->node.Next = L->link->node.Address;
        L = L->link;
    }
    L->node.Next = -1;
}

                                                                                                            04252018-22：06---第一次