1025. 反转链表 (25) python篇

爱被打了一巴掌 2022-06-17 05:16 141阅读 0赞

# 1025. 反转链表 (25) #

时间限制

300 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

CHEN, Yue

给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。

**输入格式：**

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

*Address Data Next*

其中*Address*是结点地址，*Data*是该结点保存的整数数据，*Next*是下一结点的地址。

**输出格式：**

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

**输入样例：**

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

**输出样例：**

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

# -*- coding: utf-8 -*-  
    # 思路：从给定的链首到链末共有数据个数n加1项，id为前n项，next为后n项  
    def link(address,head,li):  # 采用递归将链表所用节点依次存入列表  
        if head in address:  
            arrow = address[head]  
            li.append(arrow)  
            return link(address,arrow,li)  
        else:  
            return li  
    head,N_all,cell = input().split()  # 读取第一行输入：首项元素id，元素个数N_all，反转间隔cell  
    N_all,cell = int(N_all),int(cell)  # 将N与cell转换为整数  
    address,data = {},{}  # 初始化两个字典，其中address保存id-next关系，data保存id-data关系  
    for i in range(N_all):  # 将输入信息存入address和data中  
        a,b,c = input().split()  
        address[a],data[a] = c,b     
    # 调用link()函数将所给信息按链接顺序存入id_plus，有N_all+1个元素，末项为链尾指针，指向未知id或为-1  
    id_plus = link(address,head,[head])  # 第三项必须为[head]而不是[]，因为link()函数无法添加第一个id  
    id_plus[-1] = '-1'  # 指定链尾指针指向-1  
    N_e = len(id_plus) - 1  # id_plus中的元素个数为可链接到的元素，从首项到最后的-1，实际对应的数据个数应减1  
    num, rem = N_e // cell, N_e % cell  # 判断要对那些数据进行反转  
    if num:  # 可链接到的数据个数不小于反转间隔  
        for i in range(num):  
            id_plus[(i*cell):((i+1)*cell)] = id_plus[(i*cell):((i+1)*cell)][::-1]  # 反转  
    for k,v in enumerate(id_plus[:-1]):  # 按规定格式，打印id,data,next  
        s = '{} {} {}'.format(v,data[v],id_plus[k+1])  
        print(s)

有一个测试点超时，请大神指教！

#include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100010 //用双向静态链表来解决本问题，定义链表长度为100010 
    typedef struct Node    //定义结点         
    {
    	int data;          //存储数据 
    	int addr;          //存储当前地址 
    	int next;          //后指针，存储下一节点的地址 
    	int prior;         //前指针，存储前一节点的地址 
    }Node;
    int num,n,address,sum=1;    //num为输入节点的总数，n为每次反转节点的个数，address为第一个结点的地址，sum为计数器，记录有效节点的个数 
    void read(Node Nodes[]);   //读取数据，建立链表 
    void reverse(Node Nodes[]); //反转链表，输出结果 
    int main()
    {
    	Node Nodes[MAXSIZE];
    	scanf("%d%d%d",&address,&num,&n);
    	read(Nodes);
    	reverse(Nodes); 
    	return 0;
    } 
    
    void read(Node Nodes[])   //读取数据 
    {
    	int i,addre,addre_p;   //addre为当前结点的地址，addre_p为前一节点的地址 
    	for (i=0;i<num;i++)      //将每个结点放在地址对应下标的数组单元中，并使当前结点的后指针指向下一节点 
    	{
    		scanf("%d",&addre);
    		scanf("%d%d",&Nodes[addre].data,&Nodes[addre].next);
    		Nodes[addre].addr=addre;
    	}
    	addre=address;
    	Nodes[addre].prior=-1;   //使第一个结点的前指针指向-1 
    	addre_p=Nodes[addre].addr; //记录第一个结点的地址 
    	addre=Nodes[addre].next;   //使下一个结点成为当前结点 
    	while (addre!=-1)
    	{
    		Nodes[addre].prior=addre_p;  //使当前结点的前指针指向前一个结点 
    		addre_p=Nodes[addre].addr;   //使当前结点成为前结点 
    		addre=Nodes[addre].next;     //使下一个结点成为当前结点 
    		sum++;                       //有效结点数+1 
    	}
    }
    
    void reverse(Node Nodes[])  //反转链表，输出数据 
    {
    	int i,addre,j,addre_save,addre_prior; //addre为当前结点的地址，addre_save为每次反转前的n个结点中最后一个结点的地址， 
    	addre=address;                        //addre_prior为每次反转前的n个结点中首个结点的地址
    	if (n==1||n>sum)                      //如果每次反转结点的个数等于1或大于有效结点的个数，则不反转，依次输出即可 
    	{
    		while(addre!=-1)
    		{
    			if (Nodes[addre].next==-1)
    			printf("%05d %d %d\n",Nodes[addre].addr,Nodes[addre].data,Nodes[addre].next);
    			else
    			printf("%05d %d %05d\n",Nodes[addre].addr,Nodes[addre].data,Nodes[addre].next);
    			addre=Nodes[addre].next;
    		}
    	}else                                //否则，进行反转，每次反转n个结点 
    	{
    		for (i=0;i<sum/n;i++)           //总反转的次数为 sum/n 
    		{
    			for (j=0;j<n-1;j++)         //寻找每次反转前的n个结点中最后一个结点的地址 
    			{
    				addre=Nodes[addre].next;
    			}
    			addre_save=addre;          //保存本次反转前最后一个结点的地址 
    			if (i!=0)                  //第一次反转不输出，输出前一次反转后的n个结点中最后一个结点的地址，数据以及本次反转后第一个结点的地址（注意，这样每次反转才能衔接） 
    			printf("%05d %d %05d\n",Nodes[addre_prior].addr,Nodes[addre_prior].data,Nodes[addre].addr);
    			for (j=0;j<n-1;j++)       //除最后一个结点，依次输出本次反转后的其余结点 
    			{
    				printf("%05d %d %05d\n",Nodes[addre].addr,Nodes[addre].data,Nodes[addre].prior);
    				addre=Nodes[addre].prior;
    			}
    			addre_prior=addre;      //保存本次反转最后一个结点的地址 
    			if (Nodes[addre_save].next==-1)  //如果有效结点已用完，即没有剩余有效结点，则输出最后一个结点，注意其下一个结点地址为-1 
    			printf("%05d %d %d\n",Nodes[addre].addr,Nodes[addre].data,-1);
    			else if (i==sum/n-1)            //如果这是最后一次反转，则输出最后一个结点，注意其下一个结点的地址为不反转的第一个结点的地址 
    			printf("%05d %d %d\n",Nodes[addre].addr,Nodes[addre].data,Nodes[addre_save].next);
    			addre=Nodes[addre_save].next;  //使下次反转前的第一个结点成为当前结点 
    		}
    		for (i=0;i<sum%n;i++)    //依次输出剩余不需要反转的结点 
    		{
    			if (Nodes[addre].next==-1)
    			printf("%05d %d %d\n",Nodes[addre].addr,Nodes[addre].data,Nodes[addre].next);
    			else
    			printf("%05d %d %05d\n",Nodes[addre].addr,Nodes[addre].data,Nodes[addre].next);
    			addre=Nodes[addre].next;
    		}
    	}	
    }

用双向静态链表解决，这次不再超时