PTA(Basic Level) 1025：反转链表（C语言实现）

阳光穿透心脏的1/2处 2023-07-22 03:56 5阅读 0赞

## PTA(Basic Level) 1025：反转链表（C语言实现） ##

分析：  
最开始的思路是用两个数组，一个数组存入初始状态，另一个数组存储按后继结点排好序的结点。但是测试点5超时了，并且测试点6答案错误，翻看了几篇大家的总结，测试点6是因为可能存在游离的结点，应忽略，所以要对有效结点进行计数。  
修改之后：用一个数组存储结点，并在数组内进行排序。排序的思想是，每一次选择一个正确的结点放在适当的位置（类似选择排序）。最后当next=-1时记录有效结点个数。

#include <stdio.h>
    
    struct node
    { 
    	int address;
    	int data;
    	int next;
    }list[100000],t;
    int main()
    { 
    	int n,k,i,j,next;
    	scanf("%d%d%d",&next,&n,&k);
    	for(i=0; i<n; i++)//输入各结点
    		scanf("%d%d%d",&list[i].address,&list[i].data,&list[i].next);
    	
    	for(i=0; i<n; i++)
    		for(j=i; j<n; j++)
    			if(list[j].address == next)
    			{ 
    				t=list[i];
    				list[i]=list[j];
    				list[j]=t;
    				next=list[i].next;
    				if(next == -1)
    					n=i+1;
    				break;
    			}
    	for(i=0; i<n; i+=k)
    	{ 
    		int l=i,r=i+k-1;
    		if(r>=n)
    			break;
    		while(l<r)
    		{ 
    			t=list[l];
    			list[l]=list[r];
    			list[r]=t;
    			l++;
    			r--;
    		}
    	}
    	for(i=0; i<n; i++)
    		i==n-1?printf("%05d %d -1\n",list[i].address,list[i].data):printf("%05d %d %05d\n",list[i].address,list[i].data,list[i+1].address);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 Q2：1025 反转链表

输入样例： 00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 0000

ゞ浴缸里的玫瑰/ 2024年03月24日 10:18/ 0 赞/ 78 阅读

相关 PTA(Basic Level) 1025：反转链表（C语言实现）

PTA(Basic Level) 1025：反转链表（C语言实现）分析：最开始的思路是用两个数组，一个数组存入初始状态，另一个数组存储按后继结点排好序的结点。但是

阳光穿透心脏的1/2处/ 2023年07月22日 03:56/ 0 赞/ 6 阅读

相关 PAT乙级 1025 反转链表 (25 分)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

叁歲伎倆/ 2023年06月12日 11:23/ 0 赞/ 8 阅读

相关 LeetCode :[递归]_反转链表（C语言实现)

LeetCode :\[递归\]\_反转链表 -------------------- 题目地址： [https://leetcode-cn.com/problem

一时失言乱红尘/ 2023年03月13日 03:43/ 0 赞/ 13 阅读

相关 [206]. 反转链表(C语言)

反转一个单链表。示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你

一时失言乱红尘/ 2022年12月29日 06:37/ 0 赞/ 94 阅读

相关反转链表（c实现）

关于链表的两个小题：第一个小题： ![在这里插入图片描述][20210409191901493.png] 刚看到这个题目，一脸懵，其实这个题目考察我们对链表的理解

Love The Way You Lie/ 2022年11月17日 13:50/ 0 赞/ 167 阅读

相关 1025. 反转链表 (25) python篇

1025. 反转链表 (25) 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard

爱被打了一巴掌/ 2022年06月17日 05:16/ 0 赞/ 162 阅读

相关 1025. 反转链表 (25)

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

谁借莪１个温暖的怀抱￠/ 2022年05月26日 05:45/ 0 赞/ 160 阅读

相关 1025 反转链表 (25 分)

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

﹏ヽ暗。殇╰゛Y/ 2021年11月26日 14:20/ 0 赞/ 250 阅读

相关 PAT 1025 反转链表 (25分)（Java）

题目描述给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 `1→2→3→4→5→6`，K 为 3，则输出应该为 `3

小灰灰/ 2021年09月24日 02:06/ 0 赞/ 234 阅读