c語言單鏈表就地逆置,c語言單向鏈表逆序思路

本文目錄一覽：

• 1、寫一c語言演算法，實現對單鏈表就地逆置。
• 2、如何用c語言實現單鏈表的逆置?
• 3、單鏈表就地逆置有幾種方法
• 4、c語言用堆棧實現單鏈表的就地逆置
• 5、用c語言實現單鏈表的逆置，能將此程序詳細的解釋一下嗎？

寫一c語言演算法，實現對單鏈表就地逆置。

void inverse(LinkList L)

{

LinkList h,p,q;

q=L;

p=h=L-next; //把q指向舊鏈表頭，p，h指向第二個節點

while(p!=NULL) //倒置，把舊鏈表後一個節點的next指向前一個節點

{

h-next=q;

q=q-next;

p=p-next;

h=p;

}

L-next=NULL; //舊鏈表的頭變成了新鏈表的尾，所以next為NULL

L=h； //把L指向新鏈表的頭

}

如何用c語言實現單鏈表的逆置?

扣著的是頭節點（頭子）

車是首節點（首子）

馬是次節點（次子）

牙籤細的是指針指向，香頭髮黑的是指向，鐵頭細的是指向。

根據步驟寫程序的偽演算法（3步4循環，7張圖片搞定），如下：

以下是while循環（條件：香頭指向不為空）

第一個循環把馬弄到車前面，

第二個循環把相弄到馬前面

第三個循環把士弄到相前面

……..

直到香指向為空後停止循環。

代碼如下：只需要一個首結點pHead,就能把鏈表找到，並倒置。具體代碼如下

p香=pHead-pNext;

p鐵=p香-pNext;

p香-pNext=NULL;

P香=p鐵

while(p香 ！=NULL)

{

   p鐵=p香-pNext;

   p香-pNext=pHead-pNext;

   pHead-pNext=p香；

   p香=p鐵；

}

對照偽演算法（三步四循環），和上面的代碼是一一對應的：

第一步：香頭指向首子，鐵頭指向次子

第二步：刪掉首子指向次子（鐵頭所指向的那個子）的牙籤

第三步：香頭跟著鐵頭

以下循環條件：（條件：香頭指向不為空）

{

  循環1：鐵頭移動到香頭的下一個指向

  循環2：香頭的下一個指向首子

  循環3：頭子的下一個跟著香頭

  循環4：香頭跟著鐵頭

}

自己用道具操作幾遍，然後把流程背會，以後自己根據流程寫代碼即可。

單鏈表就地逆置有幾種方法

單鏈表就地逆置的兩種(遞歸與普通循環)

1.用遞歸演算法,對於不帶頭結點的單鏈表（a1,a2,a3,a4,a5,a6）逆置後的結果為（a6,a5,a4,a3,a2,a1）

考慮遞歸演算法，若只有一個結點，則直接返回，若存在兩個結點（a1,a2）則需要做的操作有：a2-next=a1;a1-next=NULL;return a2;

a2即新的頭結點，若有三個結點,則應先將子鏈（a2,a3）先逆置且返回該子鏈的新的頭結點，然後把子鏈（a2,a3）當作一個複合結點a2′,

組成新的二元組（a1,a2’）然後就可以執行前面相同的操作：a2′-next=a1;a1-next=NULL;return a3′;即可，多個以上的結點可同理得到，

Node *Reverse(Node *head)

{

Node *p=head;

if(p==NULL)

return NULL;　//若是空鏈表，返回空

Node *q=p-next;

if(q==NULL)

return p;　//若只有一個結點，直接返回

else

head=Reverse(q);//記錄子序列的新的頭結點

q-next=p;　//當前結點與已經逆置的子序列看成是前後的兩個結點p,q，作相應的逆置操作

p-next=NULL;

return head; //返回新的子序列的頭結點

}

2.用普通演算法循環逆置（頭插法重新建立帶頭結點的新鏈表）

Node *Reverse(Node *head)

{

Node *p=head-next;

if(p)//若鏈表不為空，則逆置，否則，空操作

{

　Node *q=p-next;

head-next=NULL;//頭結點分離

while(p)

{

p-next=head-next;　//頭插法建立鏈表

head-next=p;

if(q) //操作空指針的時候一定要非常注意，很容易出錯

{

　p=q;

　q=p-next;

}

else

　break;

}

}

return head;

}

c語言用堆棧實現單鏈表的就地逆置

#define DATATYPE int

struct Node{

DATATYPE data;

Node * next;

};

Node * reverse(Node * list){

//無頭節點;

Node * pcur,* pnext,* ppre;

ppre=NULL;

pcur=list;

while(pcur!=NULL){//將鏈表pcur用頭插法插入到一個空鏈表ppre中則實現了逆置

pnext=pcur-next;

pcur-next=ppre;

ppre=pcur;

pcur=pnext;

}

return ppre;//新的鏈表指針

}

用c語言實現單鏈表的逆置，能將此程序詳細的解釋一下嗎？

演算法的核心就是reverse函數，其它的都是輔助建立鏈表和輸出鏈表的。

從數據結構的定義來看這是一個帶頭節點的鏈表。要弄的十分明白你要耐心點畫圖看看。我簡單的說下思路：

【head是指向頭結點的】

p=head; //p最開始指向頭結點

s=p-next; //s最開始指向第一個節點

while(s-next!=NULL)//只要沒有到最後一個元素就繼續。最後一個元素的next肯定為NULL

{ //進入核心了樓主

t=s-next; //用t指向s後面的那個元素

s-next=p; //把s指向她前面那個，這個時候就實現了逆向了。而且是就地逆向。元素都沒有動的

p=s; //然後p向後移動s

s=t; //s向後移動到p

這樣到下一輪的時候又可以講下下個再指向剛才那個下一個。一次內推

}

s-next=p; //當最後一個的時候，還是要指向她的前一個。

head-next-next=NULL;//頭指針的下一個是指向原來的第一個。逆向後肯定是最後的那個了。所以最後的一個的next=NULL就明了了。

head-next=s;//s是逆序前的最後一個，逆序後是第一個，所以用頭指向他

畫個圖好好體會下，樓主！