[PAT解题报告] 反转链表 (25)

转载from http://tech-wonderland.net/blog/pat-1074-reversing-linked-list.html

其实就是个模拟题, 改怎么反转就怎么反转, 就是测试用例比较恶心, 注意输入可能不止一个链表的情况, 这种情况下, 要忽略那些不在该链表（输入中的head对应的那个链表）上的节点, 也就是有效节点数（输出的节点个数）比输入中的N要小. 题目的输入使用了数组形式的链表, 可以事先就开好一个足够大的数组, 反转的过程就是一般的反转了, 注意记录下反转以后新的链表头尾, 还有不要忘记把每段反转以后的新的链表接起来. AC代码如下:

#include <cstdio>

struct Node {
    int iData;
    int iNext;
};

const int iMaxLen = 100004;

int iHead;
int N, K;
Node NodeList[iMaxLen];

void doPrint(int iListHead) {
    while(-1 != iListHead) {
        if(NodeList[iListHead].iNext == -1) {
            printf("%.5d %d -1\n",
                iListHead,
                NodeList[iListHead].iData);
            break;
        }
        printf("%.5d %d %.5d\n",
            iListHead,
            NodeList[iListHead].iData,
            NodeList[iListHead].iNext);
        iListHead = NodeList[iListHead].iNext;
    }
}

int reverseK(int iStartHead, int iK,
             int *pHead, int *pTail) {
    if(-1 == iStartHead || iK <= 1)
        return -1;
    if(2 == iK) {
        int node1 = iStartHead;
        int node2 = NodeList[iStartHead].iNext;
        NodeList[node1].iNext = NodeList[node2].iNext;
        NodeList[node2].iNext = node1;

        *pHead = node2;
        *pTail = node1;
        return 0;
    }
    *pTail = iStartHead;
    int node1 = iStartHead;
    int node2 = NodeList[iStartHead].iNext;
    int nodeTmp = -1;
    for(int i = 0; i < iK - 1; ++i) {
        nodeTmp = NodeList[node2].iNext;
        NodeList[node2].iNext = node1;
        node1 = node2;
        node2 = nodeTmp;
    }
    *pHead = node1;
    NodeList[*pTail].iNext = node2;
    return 0;
}

void gao() {
    int iNodeTmp = iHead;
    int iEffectiveLength = 1;
    while(-1 != NodeList[iNodeTmp].iNext) {
        ++iEffectiveLength;
        iNodeTmp = NodeList[iNodeTmp].iNext;
    }

    if(K > iEffectiveLength) {
        doPrint(iHead);

    }
    N = iEffectiveLength;

    int iNewHead;
    if(K > 1) {
        int iTheHead, iTheTail;
        int iLastTail;
        // first init reverse to decide the new head
        reverseK(iHead, K, &iTheHead, &iTheTail);
        iNewHead = iTheHead;
        iLastTail = iTheTail;
        int iReverseCount = N / K - 1;
        for(int i = 0; i < iReverseCount; ++i) {
            reverseK(NodeList[iTheTail].iNext, K, &iTheHead, &iTheTail);
            NodeList[iLastTail].iNext = iTheHead;
            iLastTail = iTheTail;
        }
    }
    else
        iNewHead = iHead;
    doPrint(iNewHead);
}

int main() {
    for(int i = 0; i < iMaxLen; ++i) {
        NodeList[i].iData = 0;
        NodeList[i].iNext = -1;
    }
    scanf("%d %d %d", &iHead, &N, &K);
    int iSingleNodeAddress, iSingleNodeData, iSingleNodeNext;
    for(int i = 0; i < N; ++i) {
        scanf("%d %d %d", &iSingleNodeAddress, &iSingleNodeData, &iSingleNodeNext);
        NodeList[iSingleNodeAddress].iData = iSingleNodeData;
        NodeList[iSingleNodeAddress].iNext = iSingleNodeNext;
    }
    gao();
    return 0;
}

(1) 这次PAT最坑的一个题目吧, 输入可能不止一个链表, 有些节点不在要反转的那个链表上, 输出的时候应当忽略. 比如

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

(2) 另外注意指针的使用, 还有特例K = 1, K = N之类的情况, 因为上面的特殊坑点, 有可能是打断了的多个链表, 我们的K也有可能大于有效节点数.

全部评论

推荐最新楼层

Pandora

中山大学 C++

这题我选择狗带了...... 辛辛苦苦用链表形式做出来，居然运行超时，先缓一缓....../(ㄒoㄒ)/~~

10 回复分享

发布于 2015-10-24 16:28

简它

厦门大学 iOS开发

一口老血。。。原来我一直答案错误是因为这个。。。这个题设也没说清楚吧？

3 回复分享

发布于 2017-08-29 11:03

牛油

浙江大学 C++

自己写了一下这个题的代码，代码放博客里了pat1074(链表分组逆置)

点赞回复分享

发布于 2017-01-10 21:55

菜鸟葫芦娃

郑州大学 Java

心脏受不了

点赞回复分享

发布于 2015-11-11 16:42

黎明R

Java

你是打算用PAT找工作呢，还是考研

2 回复分享

发布于 2017-08-28 16:01

jackma23333

上海海事大学算法工程师

两种方法： 1.用递归来反转链表 #include<cstdio> #define maxn 100010 int n,k; struct Node{ int data,next; }node[maxn]; int reverse(int head){ if(node[head].next==-1)return head; int p=node[head].next,h,t; h=reverse(p);t=h; while(node[t].next!=-1)t=node[t].next; node[t].next=head; node[head].next=-1; return h; } int main(){ //freopen("A1074.txt","r",stdin); int head; scanf("%d%d%d",&head,&n,&k); while(n--){ int temp; scanf("%d",&temp); scanf("%d%d",&node[temp].data,&node[temp].next); } int p=head,h=-1,t=-1; while(p!=-1){ p=node[p].next; n++; } n++; h=head; while(n>=k){ p=h; for(int i=1;i<k;i++){ p=node[p].next; } h=node[p].next; node[p].next=-1; if(t==-1){ head=reverse(head); p=head; } else{ node[t].next=reverse(node[t].next); p=node[t].next; } while(node[p].next!=-1)p=node[p].next; t=p; node[t].next=h; n=n-k; } while(head!=-1){ printf("%05d %d ",head,node[head].data); if(node[head].next==-1)printf("-1"); else printf("%05d\n",node[head].next); head=node[head].next; } return 0; } 2.用排序来实现 #include<cstdio> #include<algorithm> using namespace std; #define maxn 100010 int n=0,k; struct Node{ int id,data,next,order=maxn; }node[maxn]; bool cmp(Node a,Node b){ return a.order<b.order; } bool cmp_reverse(Node a,Node b){ return a.order>b.order; } int main(){ //freopen("A1074.txt","r",stdin); int N,head; scanf("%d%d%d",&head,&N,&k); while(N--){ int temp; scanf("%d",&temp); scanf("%d%d",&node[temp].data,&node[temp].next); node[temp].id=temp; } int p=head; while(p!=-1){ node[p].order=n+1; p=node[p].next; n++; } sort(node,node+maxn,cmp); int r=n,i=0; while(r>=k){ sort(node+i*k,node+i*k+k,cmp_reverse); r=r-k; i++; } for(int i=0;i<n;i++){ printf("%05d %d ",node[i].id,node[i].data); if(i<n-1)printf("%05d\n",node[i+1].id); else printf("-1"); } return 0; }

点赞回复分享

发布于 2017-08-28 15:32

levinwen

北京理工大学珠海学院 C++

偏偏第一个测试用例正确，，，忧伤；

点赞回复分享

发布于 2016-01-31 19:09

zzhao

山东财经大学 Java

那应该就是你只考虑了一个链表的情况，然而是可能有多个链表的

点赞回复分享

发布于 2017-01-10 21:15