单链表实现反转的3种方法示例代码分享!

前言

单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案:

1 ,两两对换

2, 放入数组,倒置数组

3, 递归实现

代码如下:

  #include<stdio.h>  #include<malloc.h>  typedef struct Node  {     int data;   struct Node *pnext;      } Node,*pnode;  pnode CreateNode()  {     pnode phead=(pnode)malloc(sizeof(Node));   if(phead==NULL)   {    printf("fail to allocate memory");    return -1;   }   phead->pnext=NULL;   int n;   pnode ph=phead;   for(int i=0; i<5; i++)   {      pnode p=(pnode)malloc(sizeof(Node));    if(p==NULL)    {     printf("fail to allocate memory");     return -1;    }    p->data=(i+2)*19;    phead->pnext=p;    p->pnext=NULL;    phead=phead->pnext;       }   return ph;  }  int list(pnode head)  {   int count=0;   printf("遍历结果:n");   while(head->pnext!=NULL)   {    printf("%dt",head->pnext->data);    head=head->pnext;    count++;   }   printf("链表长度为:%dn",count);   return count;  }  pnode reverse2(pnode head)//两两节点之间不断交换  {   if(head == NULL || head->next == NULL)   return head;   pnode pre = NULL;   pnode next = NULL;   while(head != NULL){    next = head->next;    head->next = pre;    pre = head;    head = next;  }   return pre;  }  void reverse1(pnode head,int count)//把链表的节点值放在数组中,倒置数组  {   int a[5]= {0};     for(int i=0; i<count,head->pnext!=NULL; i++)   {    a[i]=head->pnext->data;    head=head->pnext;     }   for(int j=0,i=count-1; j<count; j++,i--)    printf("%dt",a[i]);    }    pnode reverse3(pnode pre,pnode cur,pnode t)//递归实现链表倒置  {     cur -> pnext = pre;   if(t == NULL)    return cur; //返回无头节点的指针,遍历的时候注意   reverse3(cur,t,t->pnext);    }    pnode new_reverse3(pnode head){ //新的递归转置     if(head == NULL || head->next == NULL)    return head;   pnode new_node = new_reverse3(head->next);   head->next->next = head;   head->next = NULL;   return new_node; //返回新链表头指针    }  int main()  {   pnode p=CreateNode();   pnode p3=CreateNode();   int n=list(p);   printf("1反转之后:n");   reverse1(p,n);   printf("n");   printf("2反转之后:n");   pnode p1=reverse2(p);   list(p1);   p3 -> pnext = reverse3(NULL,p3 -> pnext,p3->pnext->pnext);   printf("3反转之后:n");   list(p3);   free(p);   free(p1);   free(p3);   return 0;  }

毫无疑问,递归是解决的最简单方法,四行就能解决倒置问题。

思路参考:https://www.jb51.net/article/156043.htm

这里注意: head ->next = pre; 以及 pre = head->next,前者把head->next 指向 pre,而后者是把head->next指向的节点赋值给pre。如果原来head->next 指向 pnext节点,前者则是head重新指向pre,与pnext节点断开,后者把pnext值赋值给pre,head与pnext并没有断开。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对<计算机技术网(www.ctvol.com)!!>的支持。

—-想了解单链表实现反转的3种方法示例代码分享!全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/482778.html

(0)
上一篇 2020年11月9日
下一篇 2020年11月9日

精彩推荐