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;
}

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

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