前言

單鏈表的操作是面試中經常會遇到的問題，今天總結一下反轉的幾種方案：

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

毫無疑問，遞歸是解決的最簡單方法，四行就能解決倒置問題。

思路參考：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并沒有斷開。

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對武林網之家的支持。