[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也有可能大于有效节点数.

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 02:13
门头沟学院_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 17:21
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
6 收藏 评论
分享

全站热榜

正在热议