论坛 › C\C++交流 › 链表翻转初稿

wp231957 发表于 2022-5-8 12:09:40

链表翻转初稿

#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

int main()
{
      struct Node * node1;
      struct Node * node2;
      struct Node * node3;
      struct Node * node4;
      struct Node * node5;
      struct Node * pmove;
      node1=(struct Node*)malloc(sizeof(struct Node*));
      node2=(struct Node*)malloc(sizeof(struct Node*));
      node3=(struct Node*)malloc(sizeof(struct Node*));
      node4=(struct Node*)malloc(sizeof(struct Node*));
      node5=(struct Node*)malloc(sizeof(struct Node*));
      node1->data=1;
      node1->next=node2;
      node2->data=2;
      node2->next=node3;
      node3->data=3;
      node3->next=node4;
      node4->data=4;
      node4->next=node5;
      node5->data=5;
      node5->next=NULL;
      //输出原始链表
      pmove=node1;
      while (pmove)
      {
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      printf("\n");
      //为了翻转链表，我们需要四个指针
      struct Node * cur;
      struct Node * next;
      struct Node * pre;   //还有一个是入口指针，前面有的
      //1节点
      pre=cur=node1;
      next=cur->next;
      cur->next=0;
      //2节点
      cur=next;
      next=cur->next;
      cur->next=pre;
      pre=cur;
      //3节点
      cur=next;
      next=cur->next;
      cur->next=pre;
      pre=cur;
      //4节点
      cur=next;
      next=cur->next;
      cur->next=pre;
      pre=cur;
      //5节点
      cur=next;
      next=cur->next;
      cur->next=pre;
      pre=cur;
       //输出翻转后链表
      pmove=cur;
      while (pmove)
      {
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      printf("\n");
      return 0;
}

/*
附效果图:
   PS D:\001> ./w1
   1   2   3   4   5
   5   4   3   2   1
*/

wp231957 发表于 2022-5-8 13:05:12

第二稿：
#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

int main()
{
      struct Node * node1;
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node*));
      head->data=0;
      head->next=NULL;
      //初始化链表 ，貌似这个是头插法吧
      for(int x=0;x<10;x++)
      {
                node1=(struct Node*)malloc(sizeof(struct Node*));
                node1->data=x;
                node1->next=head;
                head=node1;
      }
      //输出原始链表
      struct Node *pmove=head;
      while (pmove)
      {
             if(pmove->next==NULL) break;
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      printf("\n");
      //为了翻转链表，我们需要四个指针
      struct Node * cur;
      struct Node * next;
      struct Node * pre;   //还有一个是入口指针，前面有的
      
      pre=cur=head;
      next=cur->next;
      cur->next=0;
      while(1)
      {
                cur=next;
                next=cur->next;
                cur->next=pre;
                pre=cur;
                if (next==NULL) break;
      }
       //输出翻转后链表
      pmove=cur->next;
      while (pmove)
      {
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      printf("\n");
      return 0;
}

/*
输出案例：
PS D:\001> ./w1
   9   8   7   6   5   4   3   2   1   0
   0   1   2   3   4   5   6   7   8   9
PS D:\001>
*/

wp231957 发表于 2022-5-8 13:29:36

wp231957 发表于 2022-5-8 13:05
第二稿：

这个版本用了尾插法，和头插法区别还是蛮大的（不像有些资料上说的没啥区别）
#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

int main()
{
      struct Node * node1;
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node*));
      head->data=0;
      head->next=NULL;
      struct Node *pmove=head;
      struct Node *head2=head;
      //初始化链表 ，准备使用尾插法
      for(int x=0;x<10;x++)
      {
                node1=(struct Node*)malloc(sizeof(struct Node*));
                node1->data=x;
                node1->next=NULL;
                head->next=node1;
                head=node1;
      }
      //输出原始链表
      pmove=pmove->next;
      while (pmove)
      {
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      printf("\n");
      //为了翻转链表，我们需要四个指针
      struct Node * cur;
      struct Node * next;
      struct Node * pre;   //还有一个是入口指针，前面有的
      
      pre=cur=head2;
      next=cur->next;
      cur->next=0;
      while(1)
      {
                cur=next;
                next=cur->next;
                cur->next=pre;
                pre=cur;
                if (next==NULL) break;
      }
       //输出翻转后链表
      pmove=cur;
      while (pmove)
      {
             if(pmove->next==NULL) break;
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      printf("\n");
      return 0;
}

/*
输出案例：
PS D:\001> ./w1
   0   1   2   3   4   5   6   7   8   9
   9   8   7   6   5   4   3   2   1   0
PS D:\001>
*/

wp231957 发表于 2022-5-9 16:19:49

wp231957 发表于 2022-5-8 13:29
这个版本用了尾插法，和头插法区别还是蛮大的（不像有些资料上说的没啥区别）

半途翻转链表（不够完美，但是终于依靠自己的代码能翻了）
#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

int main()
{
      struct Node * node1;
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node*));
      head->data=0;
      head->next=NULL;
      //初始化链表 ，貌似这个是头插法吧
      for(int x=0;x<10;x++)
      {
                node1=(struct Node*)malloc(sizeof(struct Node*));
                node1->data=x;
                node1->next=head;
                head=node1;
      }
      //输出原始链表
      struct Node *pmove=head;
      while (pmove)
      {
                if(pmove->next==NULL) break;
                printf("%4d",pmove->data);
                pmove=pmove->next;
      }
      printf("\n");
      //获取出口节点和入口节点
      struct Node * ennode=NULL;
      struct Node * exitnode=NULL;
      pmove=node1;
      int i=1;
      while (pmove)
      {
                if(i==3-1) ennode=pmove;   //要在3节点翻转 这里应该减一
                if(i==6)   exitnode=pmove;
                pmove=pmove->next;
                i++;
      }
      //半途翻转链表
      struct Node * cur;
      struct Node * next;
      struct Node * pre;   
      //入口节点
      cur=ennode;//此处ennode=node2
      pre=next=ennode->next;   //此处需要保存真正的入口地址
      cur->next=exitnode;   //跳转到需要翻转的首节点
      //入口节点下一节点
      cur=next;
      next=next->next;
      cur->next=exitnode->next;   //跳转不需翻转的节点
      pre=cur;
      while(1)
      {
                cur=next;
                next=next->next;
                cur->next=pre;
                pre=cur;
                if (cur==exitnode) break;
      }
      //输出翻转后链表
      pmove=head;
      while (pmove)
      {
                if(pmove->next==NULL) break;
                printf("%4d",pmove->data);
                pmove=pmove->next;
      }
      printf("\n");
      return 0;
}

/*
附效果图:
PS D:\001> ./w1
   9   8   7   6   5   4   3   2   1   0
   9   8   4   5   6   7   3   2   1   0
PS D:\001>
*/

wp231957 发表于 2022-5-10 10:37:32

wp231957 发表于 2022-5-9 16:19
半途翻转链表（不够完美，但是终于依靠自己的代码能翻了）

这里有个单链表循环链表的样例：
#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    struct Node * tmp=NULL;
    for(int x=10;x<20;x++)
    {
      struct Node * node1=NULL;
      node1=(struct Node*)malloc(sizeof(struct Node*));
      node1->data=x;
      if(x==10) tmp=node1;
      node1->next=head;
      head=node1;
    }
    tmp->next=head;      //构成循环链表，同时绕过头节点
    return head;
}

int main()
{
      struct Node * node1;
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node*));
      head->data=0;
      head->next=NULL;
      //输出原始链表
      struct Node *pmove=init_link(head);
      int i=0;
      while (pmove)
      {
                if(pmove->next==NULL) break;
                printf("%4d",pmove->data);
                pmove=pmove->next;
                i++;
                if(i>15) break;   //为了测试循环的效果我们选择了进行16次循环 看一下效果
      }
      printf("\n");
      
      return 0;
}

/*
附效果图:
PS D:\001> ./w3
19    18    17    16    15    14    13    12    11    10    19    18    17    16    15    14
*/

wp231957 发表于 2022-5-10 10:41:22

wp231957 发表于 2022-5-10 10:37
这里有个单链表循环链表的样例：

不知道循环链表有啥用，估计是为了双循环链表打基础吧，看一下他的遍历退出条件
#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    struct Node * tmp=NULL;
    for(int x=10;x<20;x++)
    {
      struct Node * node1=NULL;
      node1=(struct Node*)malloc(sizeof(struct Node*));
      node1->data=x;
      if(x==10) tmp=node1;
      node1->next=head;
      head=node1;
    }
    tmp->next=head;      //构成循环链表，同时绕过头节点
    return head;
}

int main()
{
      struct Node * node1;
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node*));
      head->data=0;
      head->next=NULL;
      //输出原始链表
      struct Node *pmove=init_link(head);
      struct Node * tmp=pmove;
      while (pmove)
      {
                printf("%4d",pmove->data);
                if(pmove->next==tmp) break;   //这里是循环链表的遍历退出条件
                pmove=pmove->next;
      }
      printf("\n");
      
      return 0;
}

/*
附效果图:
PS D:\001> ./w3
19    18    17    16    15    14    13    12    11    10
*/

wp231957 发表于 2022-5-10 13:19:18

wp231957 发表于 2022-5-10 10:41
不知道循环链表有啥用，估计是为了双循环链表打基础吧，看一下他的遍历退出条件

前面都错了，也不改了，就那么地吧

这个版，功能是把一个链表插入另一个链表中间

#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    for(int x=10;x<20;x++)
    {
      struct Node * node1=NULL;
      node1=(struct Node*)malloc(sizeof(struct Node));
      node1->data=x;
      node1->next=head;
      head=node1;
    }
    return head;
}

//带头节点的 头插法
struct Node * init_link2(struct Node * s)
{
    struct Node * head=s;
    for(int x=100;x<110;x++)
    {
      struct Node * node1=NULL;
      node1=(struct Node*)malloc(sizeof(struct Node));
      node1->data=x;
      node1->next=head;
      head=node1;
    }
    return head;
}


int main()
{
      struct Node * node1;
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node));
      head->data=0;
      head->next=NULL;
      //输出原始链表
      struct Node *pmove=init_link(head);
      struct Node *ins_ennode=NULL;
      struct Node *ins_exitnode=NULL;
      int i=1;
      struct Node *hhead=pmove;
      while (pmove)
      {
               // printf("%4d",pmove->data);
                if(pmove->next==NULL) break;   
                if(i==3)
                {
                  ins_ennode=pmove;             //保存链表断开后的指针
                  ins_exitnode=pmove->next;   //保存链表断开后的指针
                  break;
                }
                i++;
                pmove=pmove->next;
      }
      struct Node * head2;
      head2=(struct Node*)malloc(sizeof(struct Node));
      head2->data=0;
      head2->next=NULL;
      struct Node *pmove2=init_link2(head2);
      struct Node *sec_head=pmove2;
      while (pmove2)
      {
             //printf("%4d",pmove2->data);
             if(pmove2->next->next==NULL)    //把头节点绕出去
             break;   
             pmove2=pmove2->next;
      }
      struct Node *sec_tail=pmove2;
      //下面我们要做得就是把第二个链表插入第一个链表的第三个节点的后面
      ins_ennode->next=sec_head;
      sec_tail->next=ins_exitnode;
      //遍历插入链表后的链表 并输出
      while (hhead)
      {
                if(hhead->next==NULL) break;   
                printf("%4d",hhead->data);
                hhead=hhead->next;
      }
      return 0;
}

/*
附效果图:
PS D:\001> ./w3
19    18    17   109   108   107   106   105   104   103   102   101   100    16    15    14    13    12    11    10
*/

jhq999 发表于 2022-5-11 09:47:23

本帖最后由 jhq999 于 2022-5-11 09:51 编辑

wp231957 发表于 2022-5-10 13:19
前面都错了，也不改了，就那么地吧

这个版，功能是把一个链表插入另一个链表中间

#include <stdio.h>
#include <malloc.h>

struct Node
{
      int data;
      struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    for(int x=10;x<20;x++)
    {
      struct Node * node1=NULL;
      node1=(struct Node*)malloc(sizeof(struct Node));
      node1->data=x;
      node1->next=head;
      head=node1;
    }
    return head;
}


int main()
{
      struct Node * node1;
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node));
      head->data=0;
      head->next=NULL;
      //输出原始链表
      head=init_link(head);
        struct Node* p=head,*t=NULL;
      while (p)
      {
               
                printf("%4d",p->data);
                p=p->next;
      }

        printf("\n");
        p=t;
        while (head)
      {
                        t=head->next;
                        head->next=p;
                        p=head;
                        head=t;
        }
      head=p;
        while (p)
      {
               
                printf("%4d",p->data);
                p=p->next;

      }
        while (head)
      {
                        t=head->next;
                        free(head);
                        head=t;
        }
      return 0;
}
19    18    17    16    15    14    13    12    11    10   0
   0    10    11    12    13    14    15    16    17    18    19

wp231957 发表于 2022-5-11 09:52:02

jhq999 发表于 2022-5-11 09:47


谢谢，我现在用不了电脑，我狠好奇，你另一个链表在哪里？？？

wp231957 发表于 2022-5-11 09:52:54

jhq999 发表于 2022-5-11 09:47


你这是倒序！

wp231957 发表于 2022-5-11 09:54:30

jhq999 发表于 2022-5-11 09:47


能帮忙写一段冒泡排序吗，？？我一直好奇，究竟是排指针啊，还是移动数据呢

jhq999 发表于 2022-5-11 12:02:35

本帖最后由 jhq999 于 2022-5-11 12:12 编辑

wp231957 发表于 2022-5-11 09:54
能帮忙写一段冒泡排序吗，？？我一直好奇，究竟是排指针啊，还是移动数据呢

不是链表反转吗，怎么还需要排序？
排序的话，感觉最好交换数据

wp231957 发表于 2022-5-11 12:19:12

jhq999 发表于 2022-5-11 12:02
不是链表反转吗，怎么还需要排序？
排序的话，感觉最好交换数据

翻转思路已经清晰了，就不用再研究了
你的思路我还需要研究一下

jhq999 发表于 2022-5-11 12:55:05

本帖最后由 jhq999 于 2022-5-11 16:24 编辑

wp231957 发表于 2022-5-11 12:19
翻转思路已经清晰了，就不用再研究了
你的思路我还需要研究一下

struct Node *end=NULL,*q;//////////没测试只是个思路
                for (p=head; p->next; p=p->next)
                {
                        for (q=head;q->next!=end;q=q->next)
                        {
                                if (q->data>q->next->data)
                                {
                                        Node t=*q;
                                        q->data=q->next->data;
                                        q->next->data=t.data;
                                }
                        }
                        end=q;
                }
指针太麻烦了
       
                struct Node list;       
                list.next=head;
               
                while(1)
                {
                        int flag=1;
                        for (prv=&list,q=list.next;q->next!=end;prv=q,q=q->next)
                        {
                                if (q->data>q->next->data)
                                {
                                        flag=0;
                                        prv->next=q->next;
                                        q->next=prv->next->next;
                                        prv->next->next=q;
                                        q=prv->next;

                                }
                        }
                        //if (q!=list.next->next)
                        if(flag)
                        {
                                head=list.next;
                                break;
                        }
                        end=q;
                }
                head=list.next;

wp231957 发表于 2022-5-11 17:11:56

jhq999 发表于 2022-5-11 12:55
指针太麻烦了

成功了，成功了，谢谢，那个交换指针的方案，我还是不要研究了（估计我研究不了）

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

struct Node
{
      int data;
      struct Node *next;
};


//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    srand((int)time(NULL));
    struct Node * head=s;
    for(int x=10;x<20;x++)
    {
      struct Node * node1=NULL;
      node1=(struct Node*)malloc(sizeof(struct Node));
      node1->data=rand()%10000;
      node1->next=head;
      head=node1;
    }
    return head;
}


int main()
{
      struct Node * head;
      head=(struct Node*)malloc(sizeof(struct Node));
      head->data=0;
      head->next=NULL;
      head=init_link(head);
      //输出原始链表
      struct Node *pmove=head;
      while (pmove)
      {
             if(pmove->next==NULL) break;   
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      printf("\n");
      //准备排序
      struct Node *end=NULL,*q,*p;
      for (p=head; p->next; p=p->next)
      {
                for (q=head;q->next!=end;q=q->next)
                {
                        if (q->data>q->next->data)
                        {
                              intt=q->data;
                              q->data=q->next->data;
                              q->next->data=t;
                        }
                }
                end=q;
      }
      //输出排序后链表               
      pmove=head->next;
      while (pmove)
      {
             printf("%4d",pmove->data);
             pmove=pmove->next;
      }
      return 0;
}

/*
样例输出:
PS D:\001> ./w4
822798213215   54844272807   119615279957628
119   54828073215442761527628799582279821
*/

wp231957 发表于 2022-5-13 15:18:26

wp231957 发表于 2022-5-11 17:11
成功了，成功了，谢谢，那个交换指针的方案，我还是不要研究了（估计我研究不了）

如果仅仅是为了逆序输出一个链表还可以更简单些：
void reverse_link(struct Node * head)
{
    //这里正常是if(head==NULL) return;这里我们使用带头节点的链表，所以把头节点绕过去
    if(head->next==NULL) return;
    reverse_link(head->next);
    printf("%8d",head->data);
}

查看完整版本: 链表翻转初稿