Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

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

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

分析

第一行：00100 表示第一个节点的位置，即节点： 00100 1 12309 然后根据12309找到第二个节点：12309 2 33218，继续找，直到找到最后一个节点 68237 6 -1。
形成的单链表是 1 -> 2 -> 3 -> 4 -> 5 -> 6。第一行第二个数N=6，代表接下来会输入6个节点，K=4，意思是每4个节点逆转，余下2个节点，不足4个，故不反转。输出 4->3->2->1->5->6。

需要注意的是：

如果K=1，链表不反转
K等于链表的节点数，链表整个反转
如果链表的节点数能被K整除，则每段都要反转。
还有就是输出的时候节点的Next是和逆转后的节点相关，不是原先节点的Next,如：输入的时候节点 00000 4 99999 输出的时候应为 00000 4 33218,应为反转后节点4的下一个节点为3，而3的Address是33218。

要考虑的细节：K=1不反转，K=L 全反转，L%K == 0, 每段都反转，L%k = (K-1),多余的节点不反转。L<N，有多余节点的情况。

#include <stdio.h>

#define MAXSIZE 100001


typedef struct tagNode
{
    int addr;
    int data;
    int nextAddr;
    struct tagNode *next;
}Node;

Node *reverseList(Node *head, int k);
void PrintList(Node *p);


int main()
{
    int n;
    int k;
    int tmp;
    int num = 0;
    int startAddr;
    int data[MAXSIZE];
    int next[MAXSIZE];

    scanf("%d %d %d", &startAddr, &n, &k);



    Node a[n+1];
    a[0].nextAddr = startAddr;

    int i = 0;
    for(; i < n; i++)
    {
        scanf("%d", &tmp);
        scanf("%d %d", &data[tmp], &next[tmp]);
    }

    i = 1;
    while(1)
    {
        if(-1 == a[i-1].nextAddr)
        {
            a[i-1].next = NULL;
            num = i-1;
            break;
        }
        a[i].addr = a[i-1].nextAddr;
        a[i].data = data[a[i].addr];
        a[i].nextAddr = next[a[i].addr];
        a[i-1].next = a+i;
        i++;
    }

    Node *p = a;
    Node *pr = NULL;

    if(k <= num)
    {
        for(i=0; i<(num/k); i++)
        {
            pr = reverseList(p, k);
            p->next = pr;
            p->nextAddr = pr->addr;

            int j=0;
            while(j<k)
            {
                p = p->next;
                j++;
            }
        }
    }

    PrintList(a);


    return 0;
}


Node *reverseList(Node *head, int k)
{
    Node *first = head->next;
    Node *old = first->next;
    Node *tmp = NULL;

    int count = 1;
    while(count < k)
    {
        tmp = old->next;
        old->next = first;
        old->nextAddr = first->addr;
        first = old;
        old = tmp;
        count++;
    }

    head->next->next = old;
    if(old)
    {
        head->next->nextAddr = old->addr;
    }
    else
    {
        head->next->nextAddr = -1;
    }

    return first;
}

void PrintList(Node *p)
{
    Node *pr = p->next;
    while(pr)
    {
        if(-1 == pr->nextAddr)
        {
            printf("%05d %d -1\n", pr->addr, pr->data);
        }
        else
        {
            printf("%05d %d %05d\n", pr->addr, pr->data, pr->nextAddr);
        }

        pr = pr->next;
    }

    return;
}

参考资料

[浙江大学PTA]

[浙江大学数据结构公开课]