PAT 1074

题目 ： Reversing Linked List

分值 ： 25
难度 ： 中等题
思路 ： 每K个搞一波反转，实际上不用改next，只要你顺序动一下就好.
坑点 ： 在格式化输出时,只有第一组K的第一个 不需要printf("%05d\n",list[j].addr);
对比 ： 第一个代码是我之前做的,佩服自己当时的脑洞,第二个代码是最近做的,相比而言,以前我的
       处理方法好太多了.
做法一:
第一步：首先根据题目给的头,将一整个链表读到deal里面,(虽然他给了你N个节点,很有可能有节
点根本不在链表内)因此第一步按照题目给的头,从头读到 -1 ，并存在新的节点数组中,记录下元
素个数 count.
第二步：在你读人的这个有着count个节点的链表中每K个翻转一次,最后不足K个不翻转
第三部：如何反转呢 看下面这行 炫技代码

1
2
3
4
if( i >= count/K *K )
    pos = i ;
else
    pos = (i/K +1 )*K -(i%K) -1 ;
炫技吧,如果 i 在count最后不足K个的区间,就在原位置不动
如果 i 在普通位置，那么他就放到 (i/K +1 )*K -(i%K) -1  这个位置
                  a*K <  i < (a+1) *K 
那么  i就变成   new i = （2a+1）*K - old i
当时的脑子真的好，操作真心帅气.

这代码有炫技的成分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std ;
typedef struct Node{
    int addr ;
    int value ;
    int next ;
} Nodes ;
Nodes data[100000];
int deal[100001] ;
int deal2[100001];
int main()
{
    int head ,N ,K ;
    cin>>head >>N >> K;
    for(int i = 0 ;i< N ;i++)
    {
        int Addr , temp ,Next ;
        cin>>Addr >> temp >>Next ;
        data[Addr].addr = Addr ;
        data[Addr].value = temp ;
        data[Addr].next = Next ;
    }
    int cur = head ;
    int count = 0 ;
    while(cur != -1 )
    {
        deal[count++] = data[cur].addr ;
        cur = data[cur].next ;
    }
    int flag= 0 ;
    for(int i = 0 ; i< count ; i++)
    {
        int pos ;
        if( i >= count/K *K )
            pos = i ;
        else
            pos = (i/K +1 )*K -(i%K) -1 ;
        deal2[pos] = deal[i] ;
    }
 
    for(int i = 0 ; i< count ;i++)
    {
        int position = deal2[i] ;
        if( i )
            printf("%05d\n",data[position].addr );
        printf("%05d %d ",data[position].addr ,data[position].value );
    }
    cout<<-1<<endl ;
 }

后来的平庸代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std ;
typedef struct Node
{
    int addr ;
    int value ;
    int next ;
}Nodes ;
Nodes data[100000] ;
Nodes list[100001];
int main() {
    int s,N ,K ;
    cin >> s >> N >> K ;
    for(int i = 0 ;i< N ; i++)
    {
        int addr ;
        cin >> addr ;
        data[addr].addr =addr ;
        cin >>data[addr].value ;
        cin >>data[addr].next ;
    }
    int count = 0 ;
    int flag=0 ;
    for(int i =s ;  i!= -1 ;i =data[i].next )
    {
        list[count++] = data[i] ;
        if(count == K)
        {
            //cout <<"eee"<<endl;
            for(int j = K-1 ; j>=0 ; j--)
            {
                if(flag++)
                    printf("%05d\n",list[j].addr);
                printf("%05d %d ",list[j].addr,list[j].value);
            }
            count = 0 ;
        }
    }
    if(count<K)
    {
        for(int j = 0 ; j<count ; j++)
        {
            printf("%05d\n",list[j].addr);
            printf("%05d %d ",list[j].addr,list[j].value);
        }
    }
    cout <<"-1"<<endl ;
}