單鏈表實現反轉的3種方法示例代碼

更新時間：2019年02月11日 11:03:10 作者：攻城猿bilibili

單鏈表的反轉是常見的面試題目，下面這篇文章主要給大家介紹了關于單鏈表實現反轉的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("%d\t",head->pnext->data);
  head=head->pnext;
  count++;
 }
 printf("鏈表長度為：%d\n",count);
 return count;
}
pnode reverse2(pnode head)//兩兩節(jié)點之間不斷交換
{
 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)//把鏈表的節(jié)點值放在數組中，倒置數組
{
 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; //返回無頭節(jié)點的指針，遍歷的時候注意
 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;
}

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

思路參考：http://m.fzitv.net/article/156043.htm

這里注意： head ->next = pre; 以及 pre = head->next，前者把head->next 指向 pre，而后者是把head->next指向的節(jié)點賦值給pre。如果原來head->next 指向 pnext節(jié)點，前者則是head重新指向pre，與pnext節(jié)點斷開，后者把pnext值賦值給pre，head與pnext并沒有斷開。

總結

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

您可能感興趣的文章: