时间:2021-05-19
前言
单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案:
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("%d\t",head->pnext->data); head=head->pnext; count++; } printf("链表长度为:%d\n",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("%d\t",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;}毫无疑问,递归是解决的最简单方法,四行就能解决倒置问题。
思路参考:
这里注意: head ->next = pre; 以及 pre = head->next,前者把head->next 指向 pre,而后者是把head->next指向的节点赋值给pre。如果原来head->next 指向 pnext节点,前者则是head重新指向pre,与pnext节点断开,后者把pnext值赋值给pre,head与pnext并没有断开。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对的支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
Java实现单链表反转,递归和非递归两种形式/***反转单链表*//***定义链表**@author16026**/classNode{intval;Noden
如何把一个单链表进行反转?方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。方法2:使用3个指针遍历单链表,逐个链接点进行反转。方法3:从第2个节点到
如何把一个单链表进行反转?方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。方法2:使用3个指针遍历单链表,逐个链接点进行反转。方法3:从第2个节点到
本文实例讲述了Python实现链表反转的方法。分享给大家供大家参考,具体如下:Python实现链表反转链表反转(while迭代实现):链表的反转引入一个cur_
题目:反转一个单链表。示例:输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL进阶:你可以迭代或递归地反转链表。你能否用两