02-线性结构2 Reversing Linked List

逃离我推掉我的手 2022-07-28 00:26 130阅读 0赞

反转链表的练习：下面是自己试的代码

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node{
        int Address;
        int data;
        int nextAddress;
        struct Node *next;
    }Node;
    typedef struct Node *LinkList;
    
    int main(){
        LinkList L1 , p1 , q1;
        int i;
        int firstAddress , N , K;
        L1 = (LinkList)malloc(sizeof(Node));
        L1->next = NULL;
        scanf("%d %d %d",&firstAddress,&N,&K);
        p1 = L1;
        for(i=0;i<N;i++){
            q1 = (LinkList)malloc(sizeof(Node));
            scanf("%d %d %d",&q1->Address,&q1->data,&q1->nextAddress);
            p1->next = q1;
            p1 = q1;
        }
        p1->next = NULL;
    
        printf("测试: \n");
        p1 = L1->next;
    
        while(p1){
            printf("%d %d %d\n",p1->Address,p1->data,p1->nextAddress);
            p1 = p1->next;
        }
    
        //sort the linklist
        LinkList L2 , p2 , q2;
    
        L2 = (LinkList)malloc(sizeof(Node));
        L2->next = NULL;
        p2 = L2;
        int findAddress;
        findAddress= firstAddress;
        while(findAddress != -1){
            q2 = (LinkList)malloc(sizeof(Node));
            p1 = L1;
            while(p1 && findAddress != p1->Address){
                p1 = p1->next;
            }
            q2->Address = p1->Address;
            q2->data = p1->data;
            q2->nextAddress = p1->nextAddress;
            findAddress = p1->nextAddress;
            p2->next = q2;
            p2 = q2;
        }
        p2->next = NULL;
    
        printf("测试2: \n");
        p2 = L2->next;
    
        while(p2){
            printf("%d %d %d\n",p2->Address,p2->data,p2->nextAddress);
            p2 = p2->next;
        }
    
        //start to reserve list
        int cnt = 1;
        LinkList New , Old , temp;
        New = L2->next;
        Old = New->next;
        while(cnt < K){
            temp = Old->next;
            Old->next = New;
            New = Old;
            Old = temp;
            cnt++;
        }
        L2->next->next = Old;
        printf("反转的链表：\n");
        while(New){
            printf("%d %d %d\n",New->Address,New->data,New->nextAddress);
            New = New->next;
        }
    }

反转链表的原理用陈越老师的图,说明一下：

![Center][]

不过我没想明白，如果K反转的个数是链表的单元个数呢，比如说6。。。

最后没通过。。。。。。。。

然后

\#include <stdio.h>  
\#include <stdlib.h>  
  
typedef struct Node  
\{  
    int address;  
    int data;  
    int nextAddress;  
    struct Node \*next;  
\}Node;  
typedef struct Node \*LinkList;  
  
int main()  
\{  
    //排序前  
    LinkList L1, p1, q1;              
    L1 = (LinkList)malloc(sizeof(Node));    //创建头指针  
    L1->next = NULL;  
    int firstAddress;  
    int N, K;//N为总结点数 K为需翻转的数  
    scanf("%d %d %d", &firstAddress, &N, &K);  
    p1 = L1;  
    for(int i = 0; i < N; i++) \{  
        q1 =  (LinkList)malloc(sizeof(Node));  
        scanf("%d %d %d",&q1->address, &q1->data, &q1->nextAddress);  
        p1->next = q1;  
        p1 = q1;  
    \}  
    p1->next = NULL;  
      
//    //测试没问题  
//    printf("测试1 ：\\n");  
//    p1 = L1->next;  
//    while(p1)\{  
//        printf("%05d %d %d\\n", p1->address, p1->data, p1->nextAddress);  
//        p1 = p1->next;  
//    \}  
      
    //排序后  
    LinkList L2, p2;  
    L2 = (LinkList)malloc(sizeof(Node));    //创建头指针  
    L2->next = NULL;  
    int count = 0;  
    int findAddress = firstAddress;  
    p2 = L2;  
    while(findAddress != -1) \{            //while(count < N) \{有多余结点不在链表上没通过  
      
        q1 = L1;  
        while(q1->next) \{  
            if(q1->next->address == findAddress) \{  
                p2->next = q1->next;  
                q1->next = q1->next->next;  
                p2 = p2->next;  
                count++;  
//                printf("count = %d\\n",count);  
                findAddress = p2->nextAddress;  
//                printf("findAddress = %d\\n",findAddress);  
            \}else \{  
                q1 = q1->next;  
            \}  
        \}  
    \}  
    p2->next = NULL;  
      
//    //测试没问题  
//    printf("测试2 ：\\n");  
//    p2 = L2->next;  
//    while(p2)\{  
//        printf("%05d %d %05d\\n", p2->address, p2->data, p2->nextAddress);  
//        p2 = p2->next;  
//    \}  
    //Reversing  
    LinkList L3, p3, q3, tail;  
    L3 = (LinkList)malloc(sizeof(Node));    //创建头指针  
    L3->next = NULL;  
    //将L2以头插法插入L3  
    int n = count;                //防止有多余结点影响 n=N 会影响  
    int k = K;  
    p3 = L3;  
    p2 = L2;  
    while(n >= k) \{  
        n -= k;  
        for(int i = 0; i < k; i++) \{  
            p3->next = p2->next;  
            p2->next = p2->next->next;  
            if(i == 0)  
                tail = p3->next;  
            else  
                p3->next->next = q3;  
            q3 = p3->next;  
        \}  
        p3 = tail;  
    \}  
    p3->next = L2->next;  
      
    p3 = L3->next;  
    while(p3->next) \{  
        printf("%05d %d %05d\\n",p3->address, p3->data, p3->next->address);//不到五位数用0补全  
        p3 = p3->next;  
    \}  
    printf("%05d %d -1\\n",p3->address, p3->data);  
    return 0;  
\}

[Center]: /images/20220727/398a7a4e5de8422c8ab841c0271a7563.png