Reversing Linked List

简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_32502811/article/details/78064757 G...
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_32502811/article/details/78064757

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 (≤10
​5
​​ ) 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

我的思路是:
主要分为以下几个部分1. 读入数据,无序的方式。2. 按照输入的地址把链表排成有序的。3. 逆转的操作。 4. 数据的输出。

我的代码:

#include <stdio.h>  
#include <stdlib.h>  

//定义数据结构
typedef struct Node *PolyNode;
struct Node {
    int addr;
    int data;
    int next;
    PolyNode Next;
};
void append(int addr, int data, int next, PolyNode *pRear) {
    PolyNode P;
    P = (PolyNode)malloc(sizeof(struct Node));
    P->addr = addr;
    P->data = data;
    P->next = next;
    P->Next = NULL;
    (*pRear)->Next = P;
    *pRear = P;
}//链表尾的插入操作,测试没问题

void insert(int addr, int data, int next, PolyNode pHead) {
    PolyNode P;
    P = (PolyNode)malloc(sizeof(struct Node));
    P->addr = addr;
    P->data = data;
    P->next = next;
    P->Next = (pHead)->Next;
    (pHead)->Next = P;
}//链表头的插入操作

//对输入数据按照地址前后排序,测试后没问题
PolyNode sortList(PolyNode P, int firstAddr, int N) {
    PolyNode Pp, Rear, t;
    PolyNode p;
    p = P;
    Pp = (PolyNode)malloc(sizeof(struct Node));
    Pp->Next = NULL;
    Rear = Pp;
    int first = firstAddr;
    int end;
    while (first != -1) {
        while (p) {
            if (first == p->addr) {
                Rear->Next = p;
                append(p->addr, p->data, p->next, &Rear);
                first = p->next;
                break;
            }
            else 
                p = p->Next;
        }
        p = P;
    }
    Rear->Next = NULL;
    t = Pp; Pp = Pp->Next; free(t);
    return Pp;
}
void PrintPoly(PolyNode P) {
    while (P) {
        if(P->next == -1)
            printf("%05d %d %d\n", P->addr, P->data, P->next);
        else 
            printf("%05d %d %05d\n", P->addr, P->data, P->next);
        P = P->Next;
    }
}//结果的打印,测试无问题

//对链表按照要求逆转操作,可能有问题?
PolyNode Function(PolyNode P, int N, int K) {
    if (K > N) return NULL;
    PolyNode temp, tt;
    temp = P;
    PolyNode tP, rear, t;
    tP = (PolyNode)malloc(sizeof(struct Node));//tP是一个空de头结点
    tP->Next = NULL;
    rear = tP;
    tt = rear;
    int team = N / K;
    int i;
    PolyNode ttemp;
    while (team) {
        if (!tP) {
            append(temp->addr, temp->data, temp->next, &rear);
            temp = temp->Next;
            tt = rear;
        }
        for (i = 0; i < K-1; i++) {
            ttemp = tt;
            insert(temp->addr, temp->data, temp->next, tt);
            temp = temp->Next;
            tt = ttemp;
        }
        append(temp->addr, temp->data, temp->next, &rear);
        team = team - 1;
        tt = rear;
    }
    if (N%K != 0) {
        rear->Next = temp->Next;
    }
    t = tP; tP = tP->Next; free(t);
    return tP;
}

int main() {
    PolyNode P, Rear, t;
    PolyNode result;
    P = (PolyNode)malloc(sizeof(struct Node));
    P->Next = NULL;
    Rear = P;
    int first, N, K;
    int addr, data, next;
    scanf_s("%d %d %d", &first, &N, &K);
    int i = N;
    while (i) {
        scanf_s("%d %d %d", &addr, &data, &next);
        append(addr, data, next, &Rear);
        i = i - 1;
    }
    t = P; P = P->Next; free(t);
    result = sortList(P, first, N);

    PrintPoly(Function(result, N, K));
    getch();
    return 0;
}

按照给定的输入示例,结果最后只输出了最后三个(捂脸)!!!
还需要继续找问题。
待续···············

目录
相关文章
|
4月前
|
存储 Python
链表(Linked List)详解
链表(Linked List)详解
37 0
|
C++
【PAT甲级 - C++题解】1133 Splitting A Linked List
【PAT甲级 - C++题解】1133 Splitting A Linked List
69 0
|
C++
【PAT甲级 - C++题解】1074 Reversing Linked List
【PAT甲级 - C++题解】1074 Reversing Linked List
66 0
|
机器学习/深度学习 存储 C++
【PAT甲级 - C++题解】1052 Linked List Sorting
【PAT甲级 - C++题解】1052 Linked List Sorting
75 0
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
二叉树(Binary Tree)的二叉链表(Binary Linked List)实现
二叉树(Binary Tree)的二叉链表(Binary Linked List)实现
|
存储 C++
线性表的链式存储结构 单链表(Singly Linked List) C++
线性表的链式存储结构 单链表(Singly Linked List) C++
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 206. 反转链表 Reverse Linked List
LeetCode 206. 反转链表 Reverse Linked List