如何鏈表反轉(zhuǎn)

鏈表反轉(zhuǎn)

創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站建設(shè)、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的江蘇網(wǎng)站設(shè)計(jì)、移動媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

單向鏈表的反轉(zhuǎn)是一個經(jīng)常被問到的一個面試題，也是一個非常基礎(chǔ)的問題。比如一個鏈表是這樣的： 1-2-3-4-5 通過反轉(zhuǎn)后成為5-4-3-2-1。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當(dāng)前指針指向的下一個元素，然后將當(dāng)前節(jié)點(diǎn)元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。源代碼如下：

struct linka {

int data;

linka* next;

};

void reverse(linka* head)

{

if(head ==NULL)

return;

linka*pre, *cur, *ne;

pre=head;

cur=head-next;

while(cur)

{

ne = cur-next;

cur-next = pre;

pre = cur;

cur = ne;

}

head-next = NULL;

head = pre;

}

還有一種利用遞歸的方法。這種方法的基本思想是在反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點(diǎn)。源代碼如下。不過這個方法有一個缺點(diǎn)，就是在反轉(zhuǎn)后的最后一個結(jié)點(diǎn)會形成一個環(huán)，所以必須將函數(shù)的返回的節(jié)點(diǎn)的next域置為NULL。因?yàn)橐淖僪ead指針，所以我用了引用。算法的源代碼如下：

linka* reverse(linka* p,linka* head)

{

if(p == NULL || p-next == NULL)

{

head=p;

return p;

}

else

{

linka* tmp = reverse(p-next,head);

tmp-next = p;

return p;

}

}

編寫實(shí)現(xiàn)單向鏈表逆轉(zhuǎn)程序,要求使用最小附加空間

void?reverse()

{

Node?*prev,*current;??

prev=head;?????//從頭結(jié)點(diǎn)開始處理???

if(head==NULL)??return;

for(current=prev-next;current!=NULL;current=current-next)?//順序處理結(jié)點(diǎn)

{

current-next=prev;??//下一個結(jié)點(diǎn)的next指點(diǎn)上一個結(jié)點(diǎn)，即將鏈表反轉(zhuǎn)

prev=current;?????//保存上一個結(jié)點(diǎn)

}

head=prev;??//head為最后一個結(jié)點(diǎn)

}

單鏈表反轉(zhuǎn)的問題怎么解決（C語言）

單鏈表反轉(zhuǎn)：?

比如原鏈表為 head-1-2-3-NULL;?

反轉(zhuǎn)后：head-3-2-1-NULL;

實(shí)現(xiàn)代碼：

#include?stdio.h

#include?stdlib.h

typedef?struct?Node

{

int?data;

struct?Node?*next;

}*List;

#define?node?struct?Node

List?creat(void);

List?re(?List?head?,List?p,List?q);

void?Outlist(?List?q?);

int?main(int?argv,?char?*argc[])

{

List?head;

List?p;

List?q;

head?=?NULL;

head?=?creat();

p?=?head-next;

q?=?head;

re(head,p,q);

q?=?head-next;

Outlist(q);

system("pause");

return?0;

}

List?creat(void)

{

int?data;

List?head;

List?p;

List?q;

int?flag?=?1;

head?=?(List)malloc(sizeof(node));

q?=?head;

do

{

printf("請輸入正數(shù)(MAX_INT輸入0表示輸入結(jié)束)：");

scanf("%d",data);

fflush(stdin);

if?(?0?==?data?)

{

q-next?=?NULL;

flag?=?0;

}

else

{

p?=?(List)malloc(sizeof(node));

p-data?=?data;

q-next?=?p;

q?=?p;

}

}while(flag);

q?=?head-next;

Outlist(q);

return?head;

}

void?Outlist(?List?q?)

{

while(NULL?!=?q)

{

printf("%d?",q-data);

q?=?q-next;

}

printf("\n");

return;

}

List?re(List?head,List?p,List?q)

{

if(NULL?==?p)

{

head-next?=?q;

}

else

{

p=re(head,p-next,q-next);

p-next?=?q;

if(?head?==??q)

{

p-next?=?NULL;

}

}

return?q;

}

鏈表反轉(zhuǎn)問題

2.寫一個算法，借助棧將一個帶頭結(jié)點(diǎn)的單鏈表倒置。

要求：利用棧的特征，先沿著鏈表從頭至尾掃描一遍，將鏈表的每個結(jié)點(diǎn)的data域的值依次進(jìn)棧，然后再沿著鏈表從頭至尾掃描一遍，同時棧中元素依次出棧，并填入到鏈表的每個結(jié)點(diǎn)的data域中。

#includestdio.h

#includestdlib.h

#includemalloc.h

#define STACK_INIT_SIZE 100;

#define STACKINCREMENT 10;

typedef struct

{

int *base;

int *top;

int stacksize;

}SqStack;

typedef int ElemType;

typedef struct link

{

int data;

struct link *next;

}NODE;

NODE *creast(int n)

{

NODE *head,*q,*p;

int i=1;

head=(NODE*)malloc(sizeof(NODE));

if(head)

{

printf("input the %dth number:",i);

scanf("%d",head-data);

head-next=NULL;

p=head;

}

else

exit(0);

while(in)

{

q=(NODE*)malloc(sizeof(NODE));

q-next=NULL;

printf("input the %dth number:",++i);

scanf("%d",q-data);

p-next=q;

p=q;

}

return head;

}

void output(NODE *head)

{

NODE *p;

p=head;

do

{

printf("%d",p-data);

p=p-next;

}while(pprintf("--"));

printf("\n");

}

int InitStack(SqStack S)

{

int size = STACK_INIT_SIZE;

S.base=(int *)malloc(size*sizeof(ElemType));

if(!S.base)

return 0;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return 1;

}

int Push(SqStack S, int e)

{ if(S.top-S.base=S.stacksize)

{

int stackinvrement = STACKINCREMENT;

S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType));

if(!S.base)

return 0;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return 1;

}

int OutputStack(SqStack S)

{

return *--S.top;

}

void main()

{

int n,i;

SqStack s;

NODE *head,*p;

InitStack(s);

printf("請輸入要進(jìn)棧的元素個數(shù)是:");

scanf("%d",n);

p=head=creast(n);

output(head);

for(i=1;i=n;i++)

{

Push(s,p-data);

p=p-next;

}

p=head;

for(i=1;i=n;i++)

{

p-data=OutputStack(s);

p=p-next;

}

output(head);

}

c語言，鏈表的反轉(zhuǎn)怎么寫代碼？

單鏈表反轉(zhuǎn)很簡單，只說下思路：

1，從頭到尾循環(huán)遍歷鏈表

2，取下頭結(jié)點(diǎn)，作為尾結(jié)點(diǎn)，尾結(jié)點(diǎn)此時也為頭結(jié)點(diǎn)

3，采用前插法，將步驟二中取下的結(jié)點(diǎn)一個一個連接到頭結(jié)點(diǎn)前面，成為新的頭結(jié)點(diǎn)。

4，鏈表全部遍歷完后，新的鏈表產(chǎn)生了，是原來鏈表的反轉(zhuǎn)。

網(wǎng)站名稱：go語言單鏈表反轉(zhuǎn),go字符串反轉(zhuǎn)
當(dāng)前URL：http://chinadenli.net/article32/dsidjpc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、微信公眾號、定制開發(fā)、全網(wǎng)營銷推廣、動態(tài)網(wǎng)站、移動網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)